CF2153E题解

· · 题解

改了一个错误。

题意简述

对于 x \ge 1, k \ge 2，令 v_k(x!) 为在 k 进制下 x! 的末尾的 0 的个数。并给出 v_k(x!) 的计算方法：当 k 为质数时，

v_k(x!) = \displaystyle\sum_{j=1}^{\infty}\lfloor\cfrac{x}{k^j}\rfloor\text{。}

当 k 不为质数时，将 k 写成 k=\prod p_i^{e_i} 的形式，其中 p 为一个由质数构成的序列。则

v_k(x!) = \min_i\lfloor\cfrac{v_{p_i}(x!)}{e_i}\rfloor\text{。}

再定义 w_k(a, b) 如下：

w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) &\text{if } v_k(a!) \not=v_k(b!)\text{；} \\ 10^{100} &\text{otherwise。} \end{cases}

再定义 f_m(a, b) 如下：

f_m(a, b) = \min_{2 \le k \le m} w_k(a, b)\text{。}

给定两个正整数 n, m（2 \le n \le m \le 10^7），求：

\displaystyle\sum_{1 \le x \le n-1} f_m(x, n)\text{。}

可以保证答案严格小于 10^{100}。

分析

首先可以注意到一个东西：假设 p 是一个质数，对于所有 x<p，有 v_p(x!) = 0。因此如果 x < p \le n，则一定有 v_p(x!) = 0, v_p(n!) > 0，因此 f_m(x, n) = 0。

那么我们就可以开心地发现，设 p_0 为最大的小于 n 的质数，对于所有 x<p_0，f_m(x, n) = 0。这样就少了很多数的计算。

接下来考虑剩下的数。可以算出 n-p_0 的最大值大概是 152。

然后还有一个结论：当 a \le b 时，v_k(a!) \le v_k(b!)。这个证明很简单。你可以这样理解：b! 就是 a! 再乘上一些数，而一个数乘上另一个数，这个数末尾的 0 的个数一定是不会减少的。有了这个结论我们就可以只关注 v_k(x!) 而不去看 v_k(n!) 了（除非二者相等）。

我们再来考虑如果 k 有两个质因子 p < q，那么有 v_p(x!) \ge v_q(x!)，最终的贡献一定是由更小的 q 产生的。因此我们没必要去考虑另一个质因子。

实际上可以发现，只需要考虑 k 为素数 p 或者是形如 p^e 即可，并且这个 p 一定可以整除 [p_0, n] 中的一个数。

那么我们暴力枚举就可以解决了。

时间复杂度看似很大，实则能过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e7+5;
const int INF = 0x3f3f3f3f;

int prime[MAXN], cnt;
bool isnp[MAXN];

int n, m;

inline int v(int p, int x) {
    int res = 0;
    ll pw_p = p;
    for(; pw_p <= x; )
    {
        res += x / pw_p;
        pw_p *= p;
    }
    return res;
}

inline void init()
{
    for(int i = 2; i <= MAXN-5; i++)
    {
        if(!isnp[i]) { prime[++cnt] = i; }
        for(int j = 1; j <= cnt; j++)
        {
            const ll cur = prime[j];
            if(cur * i > MAXN-5) break;
            isnp[cur * i] = true;
            if(i % cur == 0) break;
        }
    }
}

inline void solve()
{
    ll ans = 0;
    scanf("%d%d", &n, &m);
    // find the largest prime q <= n.
    int p0 = prime[upper_bound(prime + 1, prime + cnt + 1, n) - prime - 1];

    vector<int> up; // 存放 p 满足：存在 k 使得 p0 <= p * k <= n 且 p * p > n
    for(int f = 1; (ll)f * f <= n; f++)
    {
        int p = n/f;
        p = prime[upper_bound(prime + 1, prime + cnt + 1, p) - prime - 1];
        up.emplace_back(p);
    }

    for(int x = p0; x < n; x++)
    {
        int res = INF;
        for(int p : up)
        {
            int vx = v(p, x), vn = v(p, n);
            if(vx != vn) res = min(vx, res);
        }
        // 小质数直接枚举
        for(int i = 1; i <= cnt; i++)
        {
            if(prime[i] * prime[i] > m) break;
            int p = prime[i];

            int bvx = v(p, x), bvn = v(p, n);
            for(ll e = 1, curp = p; curp <= m; e++, curp *= p)
            {
                int vx = bvx / e, vn = bvn / e;
                if(vx != vn) res = min(res, vx);
            }
        }
        ans += res;
    }
    printf("%lld\n", ans);

    return;
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

感谢 @shrimpballs 提出的错误。