HMMT 二月 2017 · 冲刺赛 · 第 20 题

HMMT February 2017 — Guts Round — Problem 20

[ 10 ] For positive integers a and N , let r ( a, N ) ∈ { 0 , 1 , . . . , N − 1 } denote the remainder of a when divided by N . Determine the number of positive integers n ≤ 1000000 for which r ( n, 1000) > r ( n, 1001) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . February 2017, February 18, 2017 — GUTS ROUND Organization Team Team ID#

解析

[ 10 ] For positive integers a and N , let r ( a, N ) ∈ { 0 , 1 , . . . , N − 1 } denote the remainder of a when divided by N . Determine the number of positive integers n ≤ 1000000 for which r ( n, 1000) > r ( n, 1001) . Proposed by: Pakawut Jiradilok Answer: 499500 ( ) 1000 Note that 0 ≤ r ( n, 1000) ≤ 999 and 0 ≤ r ( n, 1001) ≤ 1000 . Consider the = 499500 ways to 2 choose pairs ( i, j ) such that i > j .By the Chinese Remainder Theorem, there is exactly one n such that 1 ≤ n ≤ 1000 · 1001 such that n ≡ i (mod 1000) and n ≡ j (mod 1001) . Finally, it is easy to check that none of the n in the range 1000001 to 1001000 satisfy the condition, so the answer is exactly 499500.