2005 AIME II 第 4 题

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 题