蓝桥杯国赛阶乘约数题解：质因数分解与约数个数定理实战

1. 项目概述从“阶乘约数”到数论思维的实战跨越看到“蓝桥杯国赛 阶乘约数”这个标题很多参加过蓝桥杯的同学可能心头一紧或者会心一笑。这确实是蓝桥杯尤其是国赛级别中一道非常经典且具有代表性的数论题目。它不像某些纯粹的算法模板题背了就能用它考察的是你将一个看似复杂的实际问题拆解、转化为数学模型并运用基础数论知识高效解决的能力。简单来说题目会问你100!100的阶乘有多少个正约数或者给定一个正整数n求n!的约数个数。这背后直接硬算阶乘再枚举约数肯定是行不通的n稍微大一点比如20结果就会超出任何数据类型的表示范围更别提时间复杂度了。这道题的精髓在于引导你绕过“计算大数”这个表面障碍深入到整数的质因数分解这一核心性质中去。我最初接触这类题时也走了弯路总想着有没有什么巧妙的公式。后来才明白它的价值就在于让你彻底理解并熟练运用“约数个数定理”并掌握如何高效地对一个阶乘结果进行质因数分解的统计技巧。这不仅是解决一道竞赛题更是编程中处理大数相关问题的通用思路。无论你是正在备赛蓝桥杯的选手还是希望巩固数论基础的开发者吃透这个问题都能让你对整数性质、算法优化有更深的认识。接下来我就结合自己的备赛和解题经验把这道题的“里子”和“面子”都拆开来讲清楚。2. 核心思路拆解为什么不能直接算阶乘我们先来直面最朴素的想法要算n!的约数个数那我先算出n!的值再枚举从1到这个值之间的所有数看能整除多少个不就行了这个思路对于n10或许还能勉强运行但一旦n变大立刻会面临两大无法逾越的障碍。2.1 障碍一数值溢出——阶乘的增长是爆炸式的阶乘函数n!的增长速度远超指数函数。20! 约等于 2.43e18这已经接近64位无符号整数C中的unsigned long long能表示的最大值约1.84e19。而题目中的n往往可能是100甚至更大。100! 是一个大约有158位的天文数字没有任何一种基本数据类型可以直接存储它。因此“先计算出精确的n!值”这条路从物理上就被堵死了。2.2 障碍二时间复杂度过高——枚举约数不可行即便我们通过高精度算法算出了n!例如100!这个158位的数字我们要想找出它的所有约数难道要从1枚举到这个158位的数字本身吗这显然是一个O(N)的算法其中N是一个158位的数字其计算量即使对于超级计算机也是不可能完成的任务。因此我们必须寻找一个不依赖于n!具体值的计算方法。提示遇到涉及大数特别是阶乘、组合数的约数、整除问题时第一反应就应该跳出“计算具体值”的思维定式转向基于质因数分解的分析方法。这是数论问题的一个经典解题范式。2.3 破局关键约数个数定理与阶乘的质因数分解解决以上两个障碍的核心在于两个数学知识的结合约数个数定理对于一个大于1的正整数如果其质因数分解结果为 $$ N p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} $$ 其中 $p_i$ 是质数$a_i$ 是对应的指数。那么N的正约数个数为 $$ d(N) (a_1 1) \times (a_2 1) \times ... \times (a_k 1) $$ 这个定理告诉我们求约数个数本质是求质因数分解后各个质因数的指数。阶乘的质因数分解n! 的质因数分解有其特殊的规律。n! 中质因子 p 的个数可以通过勒让德定理Legendre‘s formula高效计算 $$ \text{count}(p) \left\lfloor \frac{n}{p} \right\rfloor \left\lfloor \frac{n}{p^2} \right\rfloor \left\lfloor \frac{n}{p^3} \right\rfloor ... $$ 这个公式的含义是在1到n这n个数中有 $\lfloor n/p \rfloor$ 个数至少包含一个质因子p即p的倍数有 $\lfloor n/p^2 \rfloor$ 个数至少包含两个质因子p即p^2的倍数以此类推。将它们累加起来就得到了n!中质因子p的总指数。解题思路的转化因此求n!的约数个数就转化为了以下两个步骤步骤一找出所有小于等于n的质数。步骤二对于每一个质数p利用勒让德公式计算它在n!中的指数count(p)。步骤三将所有(count(p) 1)相乘得到最终结果。这个思路完美避开了计算大数n!和枚举约数时间复杂度主要取决于找质数和计算每个质数的指数对于n100的情况计算是瞬间完成的。3. 核心算法实现与细节解析有了理论武器我们来看如何用代码实现。这里我以Python为例进行讲解因为Python的整数没有溢出问题对于最终结果相乘语法也更清晰。但算法思想是通用的C/Java实现逻辑完全一致。3.1 第一步筛选质数埃拉托斯特尼筛法我们需要所有不超过n的质数。最常用的高效方法是埃拉托斯特尼筛法。def get_primes(n): 返回小于等于n的所有质数列表。 使用埃拉托斯特尼筛法。 is_prime [True] * (n 1) # 初始化一个布尔数组假设所有数都是质数 is_prime[0] is_prime[1] False # 0和1不是质数 primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) # i是质数加入列表 # 将i的所有倍数标记为非质数 # 从i*i开始标记因为小于i*i的合数已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False return primes注意事项与优化for j in range(i * i, n 1, i):这里从i*i开始标记是常见的优化。因为对于质数i像2*i,3*i, ...,(i-1)*i这些数它们的最小质因子一定小于i所以在之前遍历更小质数比如2, 3, ...时就已经被标记为合数了。从i*i开始可以避免重复标记。当n很大时比如超过10^6i*i可能会溢出在C/Java中需要小心或者我们可以用if i * i n: break来提前终止内层循环。但在Python中整数范围很大且本题n通常不会极大所以这样写是安全的。这个算法的时间复杂度约为 O(n log log n)空间复杂度 O(n)对于n100万级别的数据都完全够用。3.2 第二步计算每个质数在n!中的指数对于筛选出的每一个质数p我们应用勒让德公式。def count_exponent_in_factorial(n, p): 计算质数p在n!的质因数分解中的指数。 使用勒让德公式。 count 0 power p while power n: count n // power power * p # 等价于计算 p, p^2, p^3, ... return count代码解析n // power就是公式中的 $\lfloor n / p^k \rfloor$。while power n:是循环条件当p^k大于n时n // power为0循环可以终止。例如计算5在100!中的指数power5:count 100 // 5 20(贡献了20个5)power25:count 100 // 25 4(贡献了4个额外的5来自25, 50, 75, 100)power125:125 100循环结束。总指数 20 4 24。3.3 第三步整合计算并输出结果将前两步结合起来并应用约数个数定理。def number_of_divisors_of_factorial(n): 计算n!的正约数个数 primes get_primes(n) # 获取所有质数 result 1 for p in primes: exp count_exponent_in_factorial(n, p) # 计算指数 result * (exp 1) # 应用约数个数定理 return result # 示例计算100!的约数个数 if __name__ __main__: n 100 ans number_of_divisors_of_factorial(n) print(f{n}! 的约数个数是{ans})运行这段代码你会得到结果。对于100!其约数个数是一个非常大的数。实操心得数据类型选择最终结果result可能非常大远超64位整数在Python中这不是问题。但在C/Java中需要使用高精度整数如Java的BigInteger来存储最终乘积或者在计算过程中对结果取模如果题目要求。本题通常要求输出具体数值所以Python有天然优势。算法正确性验证可以用小数字验证。例如计算5! 120。120的质因数分解是2^3 * 3^1 * 5^1根据定理约数个数为(31)*(11)*(11)16。你可以手动枚举120的约数1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120来验证确实是16个。用我们的程序计算number_of_divisors_of_factorial(5)也应该得到16。4. 算法优化与边界情况探讨上面的代码已经是一个正确的解法。但在竞赛中我们总是希望代码更高效、更健壮。这里有几个可以优化和注意的点。4.1 筛法的微优化对于埃拉托斯特尼筛法一个更高效的写法是只标记奇数的倍数并将数组大小减半因为除了2以外的偶数都不是质数。但对于n100这种规模优化效果微乎其微这里提一下是为了展示竞赛中常见的优化思维。def get_primes_optimized(n): 优化的筛法处理偶数情况 if n 2: return [] is_prime [True] * ((n - 1) // 2 1) # 只表示奇数is_prime[i] 对应数字 2*i1 primes [2] # 先把2加进去 for i in range(1, len(is_prime)): if is_prime[i]: p 2 * i 1 # 当前质数 if p * p n: break # 从p*p开始步长为2*p因为只关心奇数倍 start (p * p - 1) // 2 step p for j in range(start, len(is_prime), step): is_prime[j] False # 收集剩余的质数 for i in range(1, len(is_prime)): if is_prime[i]: primes.append(2 * i 1) return primes这个版本稍复杂在初次理解时使用标准筛法完全足够。4.2 计算指数的循环优化在count_exponent_in_factorial函数中我们使用while power n和power * p。这里有一个潜在的整数溢出风险在C/Java中。当p较大时power * p可能很快超出整数范围甚至变成负数或0导致死循环或错误。更安全的写法是def count_exponent_in_factorial_safe(n, p): 安全版本防止power溢出在Python中不是问题但习惯很好 count 0 temp n while temp 0: temp // p # 等价于 n // p, n // p^2, ... count temp return count这个写法更加简洁和安全。原理是一样的第一次temp // p得到 $\lfloor n/p \rfloor$第二次得到 $\lfloor n/p^2 \rfloor$直到temp为0。强烈推荐使用这种写法。4.3 处理大n与结果存储当n非常大比如10^9时我们无法用筛法获取所有质数因为空间和时间都不允许。这时我们需要换一种思路直接遍历可能的质数并计算贡献。实际上对于勒让德公式只有那些小于等于n的质数才对结果有贡献。我们可以遍历所有小于等于n的数并快速判断其是否为质数例如用试除法因为只需要判断 $\sqrt{n}$ 以内的因子。但更竞赛化的做法是我们只需要遍历所有质数p而质数p的分布是稀疏的。对于蓝桥杯国赛题目的数据范围通常n在10^5到10^6量级使用筛法是完全可行的。如果n大到10^7或以上就需要更精细的内存优化如分段筛或数学优化。关于结果n!的约数个数增长极其迅速。例如10! ≈ 3.6e6约数个数为 270。20! ≈ 2.4e18约数个数为 41040。100! 的约数个数则是一个高达几十位的数字。在编程时确保你的结果变量类型能够容纳这么大的整数Python自动处理C/Java需用高精度。5. 完整代码示例与测试将安全版本的指数计算和标准筛法结合这里给出一个鲁棒性更强的完整代码示例。def sieve_of_eratosthenes(n): 标准埃拉托斯特尼筛法返回质数列表 if n 2: return [] is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 从i*i开始标记步长为i for j in range(i * i, n 1, i): is_prime[j] False # 收集质数 primes [i for i in range(2, n 1) if is_prime[i]] return primes def count_exponent(n, p): 计算质数p在n!中的指数安全写法 cnt 0 while n: n // p cnt n return cnt def divisors_of_factorial(n): 主函数计算n!的约数个数 primes sieve_of_eratosthenes(n) result 1 for p in primes: exp count_exponent(n, p) result * (exp 1) return result if __name__ __main__: # 测试一些已知值 test_cases [1, 2, 5, 10, 20] for n in test_cases: ans divisors_of_factorial(n) print(f{n}! 的约数个数是{ans}) # 计算题目可能要求的100! n 100 ans divisors_of_factorial(n) print(f\n{n}! 的约数个数是{ans})运行这段代码你可以验证小数据并得到100!的约数个数。6. 常见问题与实战技巧在解决和教授这道题的过程中我遇到过一些常见的疑问和容易踩的坑。6.1 为什么是“质因数分解”合数不行吗这是理解的核心。约数个数定理的基石是算术基本定理任何一个大于1的自然数都可以唯一地分解为质因数的乘积。合数本身可以继续分解为更小的质数所以用合数作为因子来计数会导致重复和混乱。例如12 2^2 * 3^1。如果我们错误地认为因子包括42^2和62*3那么在计算约数组合时就会出错。只有分解到最基础的质数才能系统性地通过指数1相乘来覆盖所有可能的约数组合每个质因数可以选择0次到a_i次。6.2 勒让德公式的理解难点很多同学对公式⌊n/p⌋ ⌊n/p^2⌋ ...感到抽象。可以这样形象理解我们要统计1到n中每个数贡献了多少个质因子p。第一项⌊n/p⌋统计了至少包含1个p的数的个数。这些数每个都至少贡献了1个p。第二项⌊n/p^2⌋统计了至少包含2个p的数的个数。这些数在第一项中已经被算过一次了但它们实际上包含了两个p所以需要再补加一次贡献。例如对于p2, n10数字42^2。它在⌊10/2⌋5中被算作一个包含2的数贡献了1次它又在⌊10/4⌋2中被算作一个包含4的数需要再贡献1次。所以它总共贡献了2次正好对应其指数2。更高次项以此类推确保每个数贡献的p的个数恰好等于其质因数分解中p的指数。6.3 竞赛中的变形与扩展“阶乘约数”是一个母题它可以衍生出很多变体求n!的约数之和同样基于质因数分解。如果N p1^a1 * p2^a2 * ... * pk^ak则其所有正约数之和为 $$ \sigma(N) (1p_1p_1^2...p_1^{a_1}) \times (1p_2p_2^2...p_2^{a_2}) \times ... \times (1p_kp_k^2...p_k^{a_k}) $$ 因此在求出每个质数p在n!中的指数a后计算几何级数和再相乘即可。求n!末尾有多少个零这就是求n!中质因子5的指数因为一对2和5产生一个零而2的指数永远比5多。直接使用count_exponent(n, 5)即可。求组合数C(n, m)的约数个数组合数C(n, m) n! / (m! * (n-m)!)。我们可以分别计算n!、m!、(n-m)!的质因数分解指数形式然后对应指数相减n!的指数减去m!和(n-m)!的指数得到组合数的质因数分解最后再用约数个数定理。结果取模有时题目会要求输出结果对一个大质数如1e97取模。这时我们在最后相乘(exp1)时每一步都取模即可。特别注意取模运算只适用于最终的乘法勒让德公式中的除法是整数除法不能取模。6.4 调试与验证技巧从小测起永远先用n1, 2, 5, 10这样的小数字测试。手动计算或枚举验证结果是否正确。输出中间结果对于n10可以打印出每个质数p及其在10!中的指数检查是否正确。例如10! 3628800 2^8 * 3^4 * 5^2 * 7^1。你的程序应该输出p2, exp8 p3, exp4 p5, exp2 p7, exp1。关注边界n1时1! 1。1只有一个正约数就是1。我们的算法中get_primes(1)返回空列表result初始为1最终结果也是1这是正确的。性能测试用n100000十万测试一下你的程序运行时间。在普通电脑上使用筛法的Python代码应该在零点几秒内完成。如果太慢检查是否是筛法写成了低效的O(n^2)版本内层循环从2p开始而不是pp。这道“阶乘约数”题就像一把钥匙帮你打开了用数论思想解决编程问题的大门。它教会你的不是一段死记硬背的代码而是一种转化问题的思维将表面上的大数计算问题转化为关于整数性质的、可高效统计的问题。掌握这个思路以后再遇到“乘积的约数”、“阶乘相关的整除与余数”等问题你都能触类旁通。在蓝桥杯赛场上这类题目往往就是区分度所在因为它考察的是扎实的数学基本功和灵活的算法设计能力而非单纯的背诵模板。多练习这类题目理解其背后的每一个“为什么”你的编程和解题能力会得到实实在在的提升。