在学习了进制转换后， 𝑇 𝐽 老师提出一个问题： 𝑛 ! 转换成 𝑃 进制后，末尾会有多少零呢？      比如： 10 ! = 1 ∗ 2 ∗ . . . ∗ 10 = ( 3628800 ) 10 = ( 156574400 ) 8 = ( 1101110101111100000000 ) 2 = ( 375 𝐹 00 ) 16      10 ! 表示成十进制、八进制，未尾都有 2 个零； 10 ! 表示成二进制未尾有 8 个零。 请你编程计算 𝑛 ! 表示 𝑃 进制后末尾零的个数? 输入 一行，两个用空格隔开的整数 𝑛 , 𝑝 . 输出 一行，一个整数，表示零的个数。 样例输入 复制 10 2 样例输出 复制 8 提示 对于20%数据， 𝑝 = 10 。     对于100%数据， 2 ≤ 𝑛 ≤ 100000 , 2 ≤ 𝑝 ≤ 100000

要计算 \( n! \) 在 \( P \) 进制下末尾零的个数，等价于计算 \( n! \) 能被 \( P \) 的多少次幂整除。 设 \( P \) 的质因数分解为： \[ P = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m} \] 则 \( n! \) 在 \( P \) 进制下末尾零的个数为： \[ \min_{i=1}^m \left\lfloor \frac{\text{n! 中质因子 } p_i \text{ 的个数}}{k_i} \right\rfloor \] 步骤： 1. 对 \( P \) 进行质因数分解，得到每个质因数 \( p_i \) 及其指数 \( k_i \)。 2. 对每个 \( p_i \)，计算 \( n! \) 中 \( p_i \) 的个数（用勒让德公式）： \[ \text{cnt}_i = \sum_{t=1}^{\infty} \left\lfloor \frac{n}{p_i^t} \right\rfloor \] 3. 计算 \( \lfloor \text{cnt}_i / k_i \rfloor \)，取最小值。 注意： - 当 \( P \) 是质数时，只需计算 \( n! \) 中 \( P \) 的个数。 - 当 \( P \) 较大时，质因数分解到 \( \sqrt{P} \) 即可。 代码实现： ```python def count_factors_in_factorial(n, p): count = 0 while n: n //= p count += n return count def prime_factorization(x): factors = {} i = 2 while i * i <= x: while x % i == 0: factors[i] = factors.get(i, 0) + 1 x //= i i += 1 if x > 1: factors[x] = factors.get(x, 0) + 1 return factors def main(): n, p = map(int, input().split()) factors = prime_factorization(p) ans = float('inf') for prime, exp in factors.items(): cnt = count_factors_in_factorial(n, prime) ans = min(ans, cnt // exp) print(ans) if __name__ == "__main__": main() ``` [2026-01-11 17:49:54 | AI问答 | 549点数解答]