专栏文章

CF2153E题解

AAwsdkl
CF2153E题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minmgzi3
此快照首次捕获于
2025/12/02 04:49
3 个月前
此快照最后确认于
2025/12/02 04:49
3 个月前
查看原文
改了一个错误。

题意简述

对于 x≥1,k≥2x \ge 1, k \ge 2，令 vk(x!)v_k(x!) 为在 kk 进制下 x!x! 的末尾的 00 的个数。并给出 vk(x!)v_k(x!) 的计算方法：当 kk 为质数时，
vk(x!)=∑j=1∞⌊xkj⌋。v_k(x!) = \displaystyle\sum_{j=1}^{\infty}\lfloor\cfrac{x}{k^j}\rfloor\text{。}
当 kk 不为质数时，将 kk 写成 k=∏pieik=\prod p_i^{e_i} 的形式，其中 pp 为一个由质数构成的序列。则
vk(x!)=min⁡i⌊vpi(x!)ei⌋。v_k(x!) = \min_i\lfloor\cfrac{v_{p_i}(x!)}{e_i}\rfloor\text{。}
再定义 wk(a,b)w_k(a, b) 如下：
wk(a,b)={min⁡(vk(a!),vk(b!))if vk(a!)≠vk(b!)；10100otherwise。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}
再定义 fm(a,b)f_m(a, b) 如下：
fm(a,b)=min⁡2≤k≤mwk(a,b)。f_m(a, b) = \min_{2 \le k \le m} w_k(a, b)\text{。}
给定两个正整数 n,mn, m（2≤n≤m≤1072 \le n \le m \le 10^7），求：
∑1≤x≤n−1fm(x,n)。\displaystyle\sum_{1 \le x \le n-1} f_m(x, n)\text{。}
可以保证答案严格小于 1010010^{100}。

分析

首先可以注意到一个东西：假设 pp 是一个质数，对于所有 x<px<p，有 vp(x!)=0v_p(x!) = 0。因此如果 x<p≤nx < p \le n，则一定有 vp(x!)=0,vp(n!)>0v_p(x!) = 0, v_p(n!) > 0，因此 fm(x,n)=0f_m(x, n) = 0。
那么我们就可以开心地发现，设 p0p_0 为最大的小于 nn 的质数，对于所有 x<p0x<p_0，fm(x,n)=0f_m(x, n) = 0。这样就少了很多数的计算。
接下来考虑剩下的数。可以算出 n−p0n-p_0 的最大值大概是 152152。
然后还有一个结论：当 a≤ba \le b 时，vk(a!)≤vk(b!)v_k(a!) \le v_k(b!)。这个证明很简单。你可以这样理解：b!b! 就是 a!a! 再乘上一些数，而一个数乘上另一个数，这个数末尾的 00 的个数一定是不会减少的。有了这个结论我们就可以只关注 vk(x!)v_k(x!) 而不去看 vk(n!)v_k(n!) 了（除非二者相等）。
我们再来考虑如果 kk 有两个质因子 p<qp < q，那么有 vp(x!)≥vq(x!)v_p(x!) \ge v_q(x!)，最终的贡献一定是由更小的 qq 产生的。因此我们没必要去考虑另一个质因子。
实际上可以发现，只需要考虑 kk 为素数 pp 或者是形如 pep^e 即可，并且这个 pp 一定可以整除 [p0,n][p_0, n] 中的一个数。
那么我们暴力枚举就可以解决了。
时间复杂度看似很大，实则能过。
CPP
#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提出的错误。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...