题解:P12267 [蓝桥杯 2024 国 Python B] 儿童数

· · 题解

要计算满足 n^{61}\mid2024! 的正整数 n 的数量,关键在于对 2024! 进行质因数分解并分析约束条件。首先,通过质因数分解可以将 2024! 表示为所有不超过 2024 的质数的幂的乘积,每个质数的幂次用勒让德公式计算。比如质数 22024! 中的幂次是 2017, 质数 31008,以此类推。

然后,对于任意质数 p ,如果 n 的质因数分解中包含 p^k,那么 61k 必须小于等于 p2024! 中的幂次。这意味着 k 的取值范围是从 0⌊\frac{v_p(n!)}{m}⌋。比如对于 2k 可以取 033,共 34 种可能。最后,把所有质数的合法幂次选择数相乘,就能得到满足条件的 n 的总数。实际计算时,可以先用筛法找出 2024 以内的所有质数,然后统计每个质数的幂次并计算其合法范围,最终累乘得到结果。经过这样的计算,满足条件的 n 共有 17978112 个。