LOJ #6303. 水题 (约数 质因数)

#6303. 水题

内存限制 10 MiB 时间限制：1000 ms 标准输入输出

题目描述

给定正整数 n,kn, kn,k，已知非负整数 xxx 满足 n!modkx=0，求 xmaxx_{max}x​max​​ 。

输入格式

本题包含多组数据，请处理至文件末尾。

对于每组数据，共有一行，两个整数，表示 n,kn, kn,k。

输出格式

对于每组数据，输出一行，一个整数，表示 xmaxx_{max}x​max​​。

样例

输入样例

10 2
5000000000000000000 2
5000000000000000000 10000000000000

输出样例

8
4999999999999999981
96153846153846153

数据范围与提示

对于 40%40\%40% 的数据，k⩽2×107k \leqslant 2\times 10^7k⩽2×10​7​​，n⩽2×109n \leqslant 2\times 10^9n⩽2×10​9​​，数据组数 ⩽50 \leqslant 50⩽50。
对于 100%100\%100% 的数据，1<k⩽10131<k \leqslant 10^{13}1<k⩽10​13​​，1⩽n⩽5×10181 \leqslant n \leqslant 5\times 10^{18}1⩽n⩽5×10​18​​，数据组数 ⩽200\leqslant 200⩽200。

解题思路：

　　　　由n!%k^x=0可得:k^x必定是n!的一个约数，所以k中的质因数在$n!$肯定都存在，只是k中质因子的指数小于等于n!中的质因子的指数。

　　　 假如我们现在已经知道了k的每个质因数及其指数：P₁^C₁ P₂^C₂... Pm^Cm

　　　　我们还知道n！的每个质因子及其指数：P_1^D1P₂^D₂ ...P_m^Dm

　　　　　那么可以得到：

　　　　　　$C1*X_1<=D1$  $C_2*X_2<=D_2$ ... $C_m*X_m<=D_m$

　　　　　可以知道$$min{ X_1 X_2 ...X_m }$$便是满足条件的最大的X。

　　　　现在将问题转换为求K和n！的质因数及其指数了。

　　　　对于K的质因数和指数我们可以在$\sqrt{k}$的时间内求得，

而n！可以在$\log{n}*\sqrt{k}$的时间内得到。

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn  5000009
#define maxm
inline ll read()
{
    ll x=,f=;char ch=getchar();
    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ll)(ch-'');ch=getchar();}
    return x*f;
}
bool v[maxn];
ll prime[maxn];
ll n,m,k,ans,tot,cnt;

void Prime()
{
    for(int i=;i<=;i++)
    {
        if(!v[i])
            prime[++cnt]=i;
        for(int j=;j<=cnt&&i*prime[j]<=;j++)
        {
            v[i*prime[j]]=;
            if(i%prime[j]==)
                break;
        }
    }
}
ll Cal(ll x,ll y)
{
    if(x<y)
        return ;
    return Cal(x/y,y)+x/y;
}
int main()
{
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    Prime();
    while(scanf("%lld%lld",&n,&k)!=EOF)
    {
        ll ans=9e18;
        for(int i=;prime[i]*prime[i]<=k;i++)
        {
            if(k%prime[i]==)
            {
                cnt=;
                while(k%prime[i]==)
                    ++cnt,k/=prime[i];
                ans=min(ans,Cal(n,prime[i])/cnt);
            }
        }
        if(k!=)
            ans=min(ans,Cal(n,k));
        printf("%lld\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return ;
}

数论

数论