HMMT 二月 2008 · 冲刺赛 · 第 22 题

HMMT February 2008 — Guts Round — Problem 22

[ 10 ] For a positive integer n , let θ ( n ) denote the number of integers 0 ≤ x < 2010 such that x − n is 2009 ∑ divisible by 2010. Determine the remainder when n · θ ( n ) is divided by 2010. n =0

解析

[ 10 ] For a positive integer n , let θ ( n ) denote the number of integers 0 ≤ x < 2010 such that x − n is 2009 ∑ divisible by 2010. Determine the remainder when n · θ ( n ) is divided by 2010. n =0 ∑ 2009 Answer: 335 Let us consider the sum n · θ ( n ) (mod 2010) in a another way. Consider the n =0 2 2 2 2 sum 0 + 1 + 2 + · · · + 2007 (mod 2010). For each 0 ≤ n < 2010, in the latter sum, the term n ∑ 2009 appears θ ( n ) times, so the sum is congruent to n · θ ( n ). In other words, n =0 2009 2009 ∑ ∑ (2009)(2009 + 1)(2 · 2009 + 1) 2010 2 n · θ ( n ) = n = ≡ ( − 1) · · ( − 1) = 335 (mod 2010) . 6 6 n =0 n =0