2016 AIME II 第 11 题

Question

对正整数

N

与

k

，若存在正整数

a

，使得

a^k

恰有

N

个正因数，则称

N

为 $k$ -nice。求小于

1000

且既不是

7

-nice 也不是

8

-nice 的正整数个数。

For positive integers

N

and

k,

define

N

to be $k$ -nice if there exists a positive integer

a

such that

a^k

has exactly

N

positive divisors. Find the number of positive integers less than

1000

that are neither

7

-nice nor

8

-nice.

答案

答案：749

知识点：因数个数模运算容斥原理

难度评级：2990

小提示：

若

a = p_1^{m_1} \cdots p_t^{m_t}

，则

a^k

有

(km_1 + 1) \cdots (km_t + 1)

个因数，每个因子都比

k

的倍数多

1

If

a = p_1^{m_1} \cdots p_t^{m_t},

then

a^k

has

(km_1 + 1) \cdots (km_t + 1)

divisors, which is

1

more than a multiple of

k

大提示：

每个

N \equiv 1 \pmod{k}

也都可行（取

a = p^m

）。用容斥计数

1000

以下同余于

1

模

7

和模

8

的数。

Every

N \equiv 1 \pmod{k}

works too (take

a = p^m

). Count residues

1

mod

7

and mod

8

below

1000

by inclusion-exclusion.

解答：

若

a = p_1^{m_1} \cdots p_t^{m_t}

，则

a^k

有

(km_1 + 1)(km_2 + 1)

\cdots (km_t + 1)

个正因数，且每个因子都

\equiv 1 \pmod{k}

，所以乘积也如此。反过来，若

N = km + 1

，取

a = p^m

，则

a^k = p^{km}

恰有

N

个因数。因此

N

是

k

-nice 当且仅当

N \equiv 1 \pmod{k}

。

在

1, 2, \ldots, 999

中，有

143

个整数

\equiv 1 \pmod{7}

（即

1, 8, \ldots, 995

），有

125

个整数

\equiv 1 \pmod{8}

（即

1, 9, \ldots, 993

）。因为

\operatorname{lcm}(7, 8) = 56

，所以有

18

个整数

\equiv 1 \pmod{56}

（即

1, 57, \ldots, 953

）。由容斥，有

143 + 125 - 18 = 250

个数是

7

-nice 或

8

-nice。

因此，小于

1000

且两者都不是的正整数有

999 - 250 = 749

个。

If

a = p_1^{m_1} \cdots p_t^{m_t},

then

a^k

has

(km_1 + 1)(km_2 + 1)

\cdots (km_t + 1)

positive divisors, and each factor is

\equiv 1 \pmod{k},

so the product is too. Conversely, if

N = km + 1,

then

a = p^m

gives

a^k = p^{km}

with exactly

N

divisors. So

N

is

k

-nice exactly when

N \equiv 1 \pmod{k}.

Among

1, 2, \ldots, 999

there are

143

integers

\equiv 1 \pmod{7}

(namely

1, 8, \ldots, 995

) and

125

integers

\equiv 1 \pmod{8}

(namely

1, 9, \ldots, 993

). Since

\operatorname{lcm}(7, 8) = 56,

there are

18

integers

\equiv 1 \pmod{56}

(namely

1, 57, \ldots, 953

). By inclusion-exclusion,

143 + 125 - 18 = 250

of them are

7

-nice or

8

-nice.

Hence

999 - 250 = 749

positive integers less than

1000

are neither.

2016 AIME II 第 11 题

答案：749

难度评级：2990

小提示：

大提示：

解答：

其他年份的第 11 题