AIME 2016 II · 第 11 题

Solution

We claim that an integer $N$ is only $k$-nice if and only if $N \equiv 1 \pmod k$. By the number of divisors formula, the number of divisors of $\prod_{i=1}^n p_i^{a_i}$ is $\prod_{i=1}^n (a_i+1)$. Since all the $a_i$'s are divisible by $k$ in a perfect $k$ power, the only if part of the claim follows. To show that all numbers $N \equiv 1 \pmod k$ are $k$-nice, write $N=bk+1$. Note that $2^{kb}$ has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than $1000$ that are either $1 \pmod 7$ or $1\pmod 8$ is $143+125-18=250$, so the desired answer is $999-250=\boxed{749}$.

Solution by Shaddoll and firebolt360

Solution 2

All integers $a$ will have factorization $2^a3^b5^c7^d...$. Therefore, the number of factors in $a^7$ is $(7a+1)(7b+1)...$, and for $a^8$ is $(8a+1)(8b+1)...$. The most salient step afterwards is to realize that all numbers $N$ not $1 \pmod{7}$ and also not $1 \pmod{8}$ satisfy the criterion. The cycle repeats every $56$ integers, and by PIE, $7+8-1=14$ of them are either $7$-nice or $8$-nice or both. Therefore, we can take $\frac{42}{56} * 1008 = 756$ numbers minus the $7$ that work between $1000-1008$ inclusive, to get $\boxed{749}$ positive integers less than $1000$ that are not nice for $k=7, 8$.

Solution 3

An easier way to get $N \equiv 1 \pmod k$. Notice that they define $k$-nice to be $a^k$ has $N$ positive divisors. This implies that if $a$ is prime, then $N$ is only $k$-nice if and only if $k+1 = N$. Thus, we have proved that $N \equiv 1 \pmod k$ for $a$ prime. Then, assume $a$ is composite. Then, $a$ itself can be split into multiple factors, each containing $kx+1$ per term for the prime factorization. Then, notice that this case becomes trivial! All factors split into multiples of $k$, and obviously sums of $k$ are divisible by $k$, EXCEPT for one, that being, 1 itself. Then, we have proved that $N$ is also $k$-nice if $N \equiv 1\pmod k$. Then, as said in prior solutions, we must not have $n \equiv 1 \pmod 7$ and $n \equiv 1 \pmod 8$. Counting all $1 \pmod 7$ between 1 and 1000, we have every number in the form $7N + 1$. There are then 143 numbers that satisfy that constraint. Then, for $1 \pmod 8$, we have $8N + 1$, and there are 125 number that satisfy that. Then, to deal with $1 \pmod {56}$ (we over counted), we have 18 numbers, and thus to total number of $7$ and $8$ nice numbers is $143+125 - 18 = 250$ numbers, and our answer is $999-250 = \boxed{749}$.

~Pinotation