HMMT 二月 2016 · 团队赛 · 第 2 题

英文解析

2. [ 25 ] For positive integers n , let c be the smallest positive integer for which n − 1 is divisible by 210,
   if such a positive integer exists, and c = 0 otherwise. What is c + c + · · · + c ?nn 1 2 210
   Proposed by: Joy Zheng
   Answer: 329
   In order for c 6 = 0, we must have gcd( n, 210) = 1, so we need only consider such n . The numbernn − 1 is divisible by 210 iff it is divisible by each of 2, 3, 5, and 7, and we can consider the orderncof n modulo each modulus separately; c will simply be the LCM of these orders. We can ignore themodulus 2 because order is always 1. For the other moduli, the sets of orders arena ∈ { 1 , 2 } mod 3
   b ∈ { 1 , 2 , 4 , 4 } mod 5
   c ∈ { 1 , 2 , 3 , 3 , 6 , 6 } mod 7 .
   By the Chinese Remainder Theorem, each triplet of choices from these three multisets occurs forexactly one n in the range { 1 , 2 , . . . , 210 } , so the answer we seek is the sum of lcm( a, b, c ) over a , b , cin the Cartesian product of these multisets. For a = 1 this table of LCMs is as follows:
   1 2 3 3 6 6
   1 1 2 3 3 6 6
   2 2 2 6 6 6 6
   4 4 4 12 12 12 12
   4 4 4 12 12 12 12
   which has a sum of 21 + 56 + 28 + 56 = 161. The table for a = 2 is identical except for the top row,
   where 1 , 3 , 3 are replaced by 2 , 6 , 6, and thus has a total sum of 7 more, or 168. So our answer is
   161 + 168 = 329 .
   This can also be computed by counting how many times each LCM occurs:
   • 12 appears 16 times when b = 4 and c ∈ { 3 , 6 } , for a contribution of 12 × 16 = 192;
   • 6 appears 14 times, 8 times when c = 6 and b ≤ 2 and 6 times when c = 3 and ( a, b ) ∈
   { (1 , 2) , (2 , 1) , (2 , 2) } , for a contribution of 6 × 14 = 84;
   • 4 appears 8 times when b = 4 and a, c ∈ { 1 , 2 } , for a contribution of 4 × 8 = 32;
   • 3 appears 2 times when c = 3 and a = b = 1, for a contribution of 3 × 2 = 6;
   • 2 appears 7 times when a, b, c ∈ { 1 , 2 } and ( a, b, c ) 6 = (1 , 1 , 1), for a contribution of 2 × 7 = 14;
   • 1 appears 1 time when a = b = c = 1, for a contribution of 1 × 1 = 1.
   The result is again 192 + 84 + 32 + 6 + 14 + 1 = 329.
   °