文远知行杯D题中学数学题题解

题面

https://ac.nowcoder.com/acm/contest/9692/D

读题

首先要明确后导零(顾名思义, 很显然就是 p 进制下末尾连续0的个数).

题面中有一句话很重要: + 为了简化问题，p 保证为素数. 有了这个保证, 我们要考虑的范围就小了很多.

算法

首先我们转换一下问题, 求后导零的个数实际上就是对 n! 进行因数分解, 然后求其中 p 因子的个数(这个时候你就发现素数多么和蔼可亲了). 参照一下进制转换的过程就可以很容易的得出上述结论.

特殊情况

由于 p 是素数, 所以很容易得出 n < p 和 n == p 时后导零的个数分别为 0 和 1.

一般情况

将解记为 ans. 我们可以将 n 转写成 k * p + j 的形式, 很显然, n! 中就有因子 p, 2p, 3p, ..., kp, 因此 ans 至少为 k. 但是 k 可能是大于 p 的, 也就是可能存在 p^m 的情况, 接下来考虑这些情况. 我们将上面的数列同时除以 p 得到一个新数列 1, 2, 3, ..., k , k 同样可以转写, 我们多次重复上述步骤, 直到 k < p, 就得到了所求的解.

完整AC代码

点我查看完整代码

#include<cstdio>

typedef long long ll;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, p;
        scanf("%d%d", &n, &p);
        if (p > n)
            printf("0\n");
        else if (p == n)
            printf("1\n");
        else{
            ll ans = n / p;
            ll temp = ans;
            for (; temp; ){
                ans += temp / p;
                temp /= p;
            }
            printf("%lld\n", ans);
        } 
    }
    return 0;
}