ABC-280解题报告

D. Factorial and Multiple

题意：给你一个 $k$，求最小的 $n$ 使得 $k|n!$。$k\le 10^{12}$。

做法一

考虑将 $k$ 分解质因数，对于每项 $p^r$，都要求 $n!$ 中含有至少 $r$ 次 $p$。由于 $n!$ 的质因数单调增加，所以可以二分。对于检查某个 $n$ 是否满足条件，只需要看 $n$ 以内有多少个 $p$ 的倍数 + $n$ 以内有多少个 $p^2$ 的倍数……以此类推。对于每个 $p^r$ 取对 $n$ 限制最大的那个即可，最后可能剩下的一个 $>\sqrt{n}$ 的质因数特判一下。时间复杂度 $\sqrt{n}+\log^3(n)$。

检查 $n!$ 中 $p$ 的次数使用的方法被称为“勒让德定理(Legendre’s Formula)”，描述是： $n!$ 中 $p$ 的次数等于 $\sum\limits_{k\ge 1} \left\lfloor\frac{n}{p^k}\right\rfloor$。证明：首先对于所有的 $p$ 的倍数都要计算一次贡献，为 $\left\lfloor\frac{n}{p}\right\rfloor$；然后对于所有 $p^2$ 的倍数，我们希望计算两次贡献，而当前只计算了一次，所以需要再加上 $\left\lfloor\frac{n}{p^2}\right\rfloor$ 的贡献。以此类推得到上述结论。

勒让德定理有一个扩展形式，描述为：$n!$ 中 $p$ 的次数等于，$n$ 减去“将 $n$ 转化为 $p$ 进制后的各位之和”，再除以 $p-1$。证明：容易发现 $\left\lfloor\frac{n}{p}\right\rfloor$ 即为 $n$ 在 $p$ 进制下右移一位的结果，$\left\lfloor\frac{n}{p^2}\right\rfloor$ 即为 $n$ 在 $p$ 进制下右移两位的结果，以此类推。故对于 $n$ 的第 $i$ 位（从低到高），它会分别在第 $i-1,i-2,i-3,\cdots,0$ 位统计贡献，故第 $i$ 位 $e_i$ 造成的贡献为 $\sum\limits_{j<i} e_i\cdot p^j=e_i\cdot \frac{p^i-1}{p-1}$，而总贡献即为每一位的贡献之和（$x$ 为位数）：

$$\frac{\sum\limits_{i=1}^{x}e_ip^i-\sum\limits_{i=1}^{x}e_i}{p-1}=\frac{(n-e_0)-(\sum\limits_{i=0}^x e_i-e_0)}{p-1}=\frac{n-\sum\limits_{i=0}^x e_i}{p-1}$$

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int k,ans=0;
    cin>>k;
    for(int i=2;i*i<=k;i++) {
        if(k%i!=0) continue;
        int cnt=0,l=1,r=k;
        while(k%i==0) cnt++,k/=i;
        while(l<r) {
            int mid=(l+r)/2,now=0;
            for(int x=i;x<=mid;x*=i) {
                now+=mid/x;
                if(now>=cnt) break;
            }
            if(now>=cnt) r=mid;
            else l=mid+1;
        }
        ans=max(ans,l);
    }
    if(k!=1) ans=max(ans,k);
    cout<<ans<<endl;
    return 0;
}

这个做法有许多本质相同的变种，如：每次将 $mid\text{/=}x$ 而不是 $x\text{*=}i$；在外部二分，内部整体 check；check 时每步跳跃 $i$ 地枚举阶乘等。

每次减小 $mid$ By potato167

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;
    //cin>>t;
    rep(i,0,t) solve();
}

void solve(){
    ll K;
    cin>>K;
    ll ans=0;
    auto p=Prime_factorization(K);
    for(auto x:p){
        ll l=1,r=K;
        while(r-l>1){
            ll med=(r+l)/2;
            ll D=med;
            ll tmp=0;
            while(med){
                med/=x.first;
                tmp+=med;
            }
            if(tmp<x.second) l=D;
            else r=D;
        }
        chmax(ans,r);
    }
    cout<<ans<<"\n";
}

外部二分，整体 check By IH19980412

void solve(){
    int k;cin>>k;
    auto p = pollard_rho_fast::factorize2(k);
    int lb=0, ub = 1e12+5;
    while(ub-lb>1){
        int mid=(lb+ub)/2;
        for(auto x:p){
            int num=x.a;
            int cnt=x.b;
            int t=0;
            int now=mid;
            while(now){
                t += now / num;
                now /= num;
            }
            if(t < cnt) goto fail;
        }
        ub=mid;continue;
        fail:;lb=mid;
    }
    o(ub);
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);
    int t; t = 1; //cin >> t;
    while(t--) solve();
}

每步跳跃枚举阶乘 By ygussany

#include <stdio.h>

void chmax(long long* a, long long b)
{
    if (*a < b) *a = b;
}

int main()
{
    long long K;
    scanf("%lld", &K);

    int j;
    long long i, ans = 1, tmp, tmpp;
    for (i = 2; i * i <= K; i++) {
        if (K % i != 0) continue;
        for (j = 0; K % i == 0; j++, K /= i);
        for (tmp = i; 1; tmp += i) {
            for (tmpp = tmp / i, j--; tmpp % i == 0; tmpp /= i, j--);
            if (j <= 0) break;
        }
        chmax(&ans, tmp);
    }
    if (K >= 2) chmax(&ans, K);
    printf("%lld\n", ans);
    fflush(stdout);
    return 0;
}

提前跑一层最后再加回来 By daisybunny

#include<bits/stdc++.h>
using namespace std;
map<long long,long long> mp;
long long k;
vector<long long> v;
long long ma;
void fjzys(long long a)
{
    long long x=a;
    for(long long t=2;t*t<=a;t++)
    {
        //cout<<t*t<<endl;
        if(x%t==0)
            v.push_back(t);
        while(x%t==0)
        {
            mp[t]++;
            x/=t;
            //cout<<t<<" ";
        }
    }
    if(x!=1)
    {
        v.push_back(x);
        mp[x]++;
    }
}
int main()
{
    cin>>k;
    fjzys(k);
    for(long long t=0;t<v.size();t++)
    {
        long long sum=0;
        for(long long i=1;;i++)
        {
            long long x=i;
            long long b=0;
            while(x%v[t]==0)
            {
                x/=v[t];
                b++;
            }
            sum+=b+1;//提前跑了一层
            if(sum>=mp[v[t]])
            {
                ma=max(i*v[t],ma);//补回来
                break;
            }
        }
    }
    cout<<ma;
    return 0;
}

做法二

考虑直接枚举 $n$，维护当前 $n!$ 对 $k$ 的模数，直到第一次为 $0$ 时满足条件。这个做法直接写肯定会超时，但注意到当 $n$ 比较大时就将大部分情况覆盖地非常全了，唯一一种没有覆盖到的情况只能是 $k$ 有一个非常大的质因子。此时该质因子只能出现一次（因为 $>\sqrt{k}$），所以答案的 $n=$ 该质因子。

正确性证明：

假设 $k$ 在 $\sqrt{k}$ 以内的某个质因子 $p^r$，则在枚举 $n$ 时至少会在每个 $p$ 的倍数被覆盖一次，所以 $n$ 保证正确性的枚举上界为最大的 $pr$。有 $r=\log_p(k)$，所以枚举上界为 $p\log_p(k)$，其在 $p>2$ 时单调递增，所以最坏情况有 $\begin{cases}p=2,r=\log_2(k)\\p=\sqrt{k},r=2\end{cases}$，所以枚举到 $2\sqrt{k}$ 即可保证正确性。

另一种证法：在 $10^4\sim 10^6$ 内的质因数最多出现两个，所以到 $2\times 10^6$ 即可保证正确性；在 $10^4$ 以内的质因数最多也只能有不超过 $100$ 个，所以到 $10^6$ 就能保证正确性

By noimi

int main() {
    LL(k);
    auto f = factor(k);
    ll ma = 0;
    rep(i, si(f)) { chmax(ma, f[i].fi); }

    ll now = 1;
    rep(i, 1, ten(8)) {
        now = now * i % k;
        if(!now) {
            OUT(i);
            exit(0);
        }
    }
    OUT(ma);
}

还有一种不同的实现，每次枚举到一个数时将它能覆盖到的 $k$ 的质因数覆盖掉，即将 $k\text{/=}\gcd(i,k)$。当积累的覆盖足够多，直到能将 $k$ 的所有质因数全部覆盖完，就达到了 $i!$ 是 $k$ 的倍数的目标。

By physharp

k=int(input())
import math
for n in range(1,2000001):
  k//=math.gcd(k,n)
  if k<2: exit(print(n))
print(k)