题目

用排列组合中的乘法原理
甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个?
可否不用枚举法？

提问时间：2020-11-02

答案

甲、乙两数的公约数一定是其最大公约数60的因子,因此本题相当于求60的因子有多少个.这是有公式的.一般的结论是：
如果自然数n的质因数分解为 n = p1^n1 * p2^n2 * ... * pk^nk,那么n的因子数为 (n1+1)(n2+1)...(nk+1).
上式的证明就是用乘法原理.因为n的所有因子一定是如下形式：
p1^m1 * p2^m2 * ... * pk^mk,
其中m1,m2,...,mk的取值范围分别是
m1∈[0,n1], m2∈[0,n2], ..., mk∈[0,nk],
给定不同的m1,m2,...,mk就得到不同的因子,所以n的所有因子的个数为(n1+1)(n2+1)...(nk+1).
例如对于60,它的质因数分解为60=2^2*3^1*5^1,所以60的因子数就是
(2+1)(1+1)(1+1)=12.