来自顾思宁的问题
【用排列组合中的乘法原理甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个?可否不用枚举法?】
用排列组合中的乘法原理
甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个?
可否不用枚举法?
1回答
2019-10-31 07:44
【用排列组合中的乘法原理甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个?可否不用枚举法?】
用排列组合中的乘法原理
甲、乙两个自然数的最大公约数是60,则甲、乙两数的公约数共有多少个?
可否不用枚举法?
甲、乙两数的公约数一定是其最大公约数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.