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)(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 题