2010 AMC 12B 第 25 题

Question

对每个整数

n\ge2

，令

\operatorname{pow}(n)

为整除

n

的最大质数的最大幂。例如，

\operatorname{pow}(144)=\operatorname{pow}(2^4\cdot3^2)=3^2

。求最大的整数

m

，使得

2010^m

整除

\prod_{n=2}^{5300}\operatorname{pow}(n)\text{？}

For every integer

n\ge2,

let

\operatorname{pow}(n)

be the largest power of the largest prime that divides

n.

For example,

\operatorname{pow}(144)=\operatorname{pow}(2^4\cdot3^2)=3^2.

What is the largest integer

m

such that

2010^m

divides

\prod_{n=2}^{5300}\operatorname{pow}(n)?

74

75

76

77

78

答案：D

知识点：质因数分解质数区间内整数计数

难度评级：2640

小提示：

2010=2\cdot3\cdot5\cdot67

；求乘积中每个质数的指数并取最小值

2010=2\cdot3\cdot5\cdot67;

find the exponent of each prime in the product and take the minimum

大提示：

\operatorname{pow}(n)

只有在

p

是

n

的最大质因数时才会贡献质数

p

\operatorname{pow}(n)

contributes a prime

p

only when

p

is the largest prime factor of

n

解答：

因为

2010=2\cdot3\cdot5\cdot67

，将乘积写成

2^A3^B5^C67^D

乘以一个与这四个质数都互质的因子；于是

m=\min(A,B,C,D)

。

质数 $2$ ： 只有当

n=2^k

时，

\operatorname{pow}(n)

才是

2

的幂。因为

2^{12}=4096\lt5300\lt2^{13}

，所以

k=1,\ldots,12

贡献

A=1+2+\cdots+12=78

。

质数 $67$ ： 当

67

是最大质因数时，

\operatorname{pow}(n)=67

，即

n=67j

，其中

1\le j\le79

，且

j

的每个质因数都至多为

67

；排除

j=67, 71, 73, 79

后剩下

75

个值。唯一满足

\operatorname{pow}(n)=67^2

的

n

是

n=67^2\lt5300

，再贡献

2

。所以

D=75+2=77

。

质数 $3$ ： 对于

n=2^a3^b

，当

b=1,2,3,4

时，允许的指数

a

的个数分别为

11,10,8,7

，仅这些项就贡献

\begin{aligned} B&\ge11+2\cdot10 \\ &\quad+3\cdot8+4\cdot7=83 \end{aligned}\text{。}

质数 $5$ ： 写成

n=2^a3^c5^b

。当

b=1

时，对

c=0,\ldots,6

的计数总和为

11+9+7+6+4+3+1=41

。当

b=2

时，计数总和为

8+7+5+3+2=25

，每个贡献两个因数

5

。因此

C\ge41+2\cdot25=91

。

所以

m=\min(78,B,C,77)=77

。

因此，正确答案是 D。

Since

2010=2\cdot3\cdot5\cdot67,

write the product as

2^A3^B5^C67^D

times a factor coprime to all four primes; then

m=\min(A,B,C,D).

Prime $2:$

\operatorname{pow}(n)

is a power of

2

only when

n=2^k.

Since

2^{12}=4096\lt5300\lt2^{13},

the values

k=1,\ldots,12

contribute

A=1+2+\cdots+12=78.

Prime $67:$

\operatorname{pow}(n)=67

when

67

is the largest prime factor, i.e.

n=67j

with

1\le j\le79

and every prime factor of

j

at most

67;

excluding

j=67, 71, 73, 79

leaves

75

values. The one

n

with

\operatorname{pow}(n)=67^2

is

n=67^2\lt5300,

adding

2.

So

D=75+2=77.

Prime $3:$ For

n=2^a3^b

with

b=1,2,3,4,

the numbers of allowable exponents

a

are

11,10,8,7,

respectively. These terms alone contribute

\begin{aligned} B&\ge11+2\cdot10 \\ &\quad+3\cdot8+4\cdot7=83. \end{aligned}

Prime $5:$ Write

n=2^a3^c5^b.

For

b=1,

the counts over

c=0,\ldots,6

total

11+9+7+6+4+3+1=41.

For

b=2,

the counts total

8+7+5+3+2=25,

each contributing two factors of

5.

Hence

C\ge41+2\cdot25=91.

Therefore

m=\min(78,B,C,77)=77.

Thus, the correct answer is D.

2010 AMC 12B 第 25 题

答案：D

难度评级：2640

小提示：

大提示：

解答：

其他年份的第 25 题