HMMT 十一月 2020 · 冲刺赛 · 第 17 题

17. [10] Let N denote the set of positive integers greater than 1. Let f : N → N be a function such

1 > 1 > 1 that f ( mn ) = f ( m ) f ( n ) for all m, n ∈ N . If f (101!) = 101!, compute the number of possible values 1 of f (2020 · 2021). Proposed by: Sheldon Kieren Tan Answer: 66 Solution: For a prime p and positive integer n , we let v ( n ) denote the largest nonnegative integer k p k such that p | n . Note that f is determined by its action on primes. Since f (101!) = 101!, by counting prime factors, f must permute the set of prime factors of 101!; moreover, if p and q are prime factors of 101! and f ( p ) = q , we must have v (101!) = v (101!). This clearly gives f (2) = 2, f (5) = 5, so it suffices p q 2 2 to find the number of possible values for f (43 · 47 · 101). (We can factor 2021 = 45 − 2 = 43 · 47.) There are 4 primes with v (101!) = 2 (namely, 37, 41, 43, 47), so there are 6 possible values for p f (43 · 47). Moreover, there are 11 primes with v (101!) = 1 (namely, 53, 59, 61, 67, 71, 73, 79, 83, 89, p 97, 101). Hence there are 66 possible values altogether.