编程揭秘：计算 𝑛! 在 𝑃 进制下末尾零个数的方法与代码实现

要计算 \( 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() ``` ######[AI问答 | 549点数解答 | 2026-01-11 17:49:54]