Question

用排列组合中的乘法原理

甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个？
可否不用枚举法？

Answer 1

甲、乙两数的公约数一定是其最大公约数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。

Answer 2

甲乙的公约数为甲乙最大公约数的约数，
60=2^2*3*5
其约数有(2+1)*(1+1)*(1+1)=12个

Answer 3

1,2,3,4,5,6,10,12,15,20,30,60
共有12个