Question

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.

答案

Solution:

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 Problem 11

Solution:

Problem 11 in Other Years