Question

求至少整除 $10^{10}$ 、 $15^7$ 、 $18^{11}$ 中一个数的正整数个数。

Find the number of positive integers that are divisors of at least one of $10^{10},$ $15^7,$ $18^{11}.$

答案

答案：435

知识点：因数个数容斥原理最大公约数

难度评级：2230

小提示：

先由质因数分解数出每个数的因数个数，再修正重复计数。

Count the divisors of each number from its prime factorization, then fix the overcounting

大提示：

两个数的公共因数恰好是它们最大公因数的因数，例如 $\gcd(10^{10}, 15^7) = 5^7$ 。

The common divisors of two of the numbers are exactly the divisors of their gcd, e.g. $\gcd(10^{10}, 15^7) = 5^7$

解答：

由分解式 $10^{10} = 2^{10} 5^{10}$ 、 $15^7 = 3^7 5^7$ 以及 $18^{11} = 2^{11} 3^{22}$ ，它们的因数个数分别为 $11 \cdot 11 = 121$ 、 $8 \cdot 8 = 64$ 和 $12 \cdot 23 = 276$ 。

两个数的公共因数恰好是它们最大公因数的因数： $\gcd(10^{10}, 15^7) = 5^7$ 有 $8$ 个因数， $\gcd(10^{10}, 18^{11}) = 2^{10}$ 有 $11$ 个， $\gcd(15^7, 18^{11}) = 3^7$ 有 $8$ 个。只有 $1$ 同时整除三个数。

由容斥原理，所求个数为 $121 + 64 + 276$ $- 8 - 11 - 8 + 1$ $= 435$ 。

From the factorizations $10^{10} = 2^{10} 5^{10},$ $15^7 = 3^7 5^7,$ and $18^{11} = 2^{11} 3^{22},$ the divisor counts are $11 \cdot 11 = 121,$ $8 \cdot 8 = 64,$ and $12 \cdot 23 = 276.$

The divisors common to two of the numbers are exactly the divisors of their gcd: $\gcd(10^{10}, 15^7) = 5^7$ has $8$ divisors, $\gcd(10^{10}, 18^{11}) = 2^{10}$ has $11,$ and $\gcd(15^7, 18^{11}) = 3^7$ has $8.$ Only $1$ divides all three numbers.

By inclusion-exclusion, the count is $121 + 64 + 276$ $- 8 - 11 - 8 + 1$ $= 435.$

2005 AIME II 第 4 题

答案：435

难度评级：2230

小提示：

大提示：

解答：

其他年份的第 4 题