PUMaC 2016 · 数论（B 组） · 第 4 题

PUMaC 2016 — Number Theory (Division B) — Problem 4

For a positive integer n , let P ( n ) be the product of the factors of n (including n itself). A positive integer n is called deplorable if n > 1 and log P ( n ) is an odd integer. How many n factors of 2016 are deplorable?

解析

For each d | n , pair d with and observe their product is n . Thus, the product of all of the d factors of n is n to the power of half the number of factors of n (this also holds for perfect √ squares; you pair n with itself). Thus, log P ( n ) is equal to half the number of factors of n . n This is and odd integer if and only if the number of factors of n is divisible by 2 but not 4. p k 2 k 1 m Recall that if n = p p . . . p for primes p through p , then the number of factors of n is 1 m 1 2 m ( k + 1)( k + 1) . . . ( k + 1). This is divisible by 2 but not 4 if all of the k are even except one 1 2 m i of them, which is 1 (mod 4). 5 2 k k k 2 3 7 Note that 2016 = 2 · 3 · 7. Let n | 2016 and write n = 2 3 7 . If k ≡ 1 (mod 4) then either 2 k = 1 or k = 5; either way, k is either 0 or 2 and k is 0, giving 4 possibilities. If k ≡ 1 2 2 3 7 3 (mod 4) then k = 1; furthermore, k is either 0, 2, or 4 and k is 0, giving 3 possibilities. 3 2 7 Finally, if k ≡ 1 (mod 4) then k = 1; furthermore, k is either 0, 2, or 4 and k is either 0 7 7 2 3 or 2, giving 6 possibilities. Thus, the answer is 6 + 3 + 4 = 13 . Problem written by Eric Neyman.