钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

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

题面

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

读题

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

题面中有一句话很重要:

  • 为了简化问题,p 保证为素数.
    有了这个保证, 我们要考虑的范围就小了很多.

算法

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

特殊情况

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

一般情况

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

完整AC代码