PUMaC 2015 · 团队赛 · 第 13 题
PUMaC 2015 — Team Round — Problem 13
题目详情
- [ 8 ] We define b x c as the largest integer less than or equal to x . What is ⌊ ⌋ 2017015 5 mod 1000? 2015 5 + 7
解析
- [ 8 ] We define b x c as the largest integer less than or equal to x . What is ⌊ ⌋ 2017015 5 mod 1000? 2015 5 + 7 Solution: We proceed with division. We have that: 2017015 2015000 2 2015000 − 2015 5 7 · 5 7 · 5 2015000 2015000 2015000 − 2015 = 5 − = 5 − 7 · 5 + 2015 2015 2015 5 + 7 5 + 7 5 + 7 1001 0 7 · 5 2015000 2015000 − 2015 1000 2015000 − 2015 ∗ 1000 = 5 − 7 · 5 + · · · + 7 · 5 − 2015 5 + 7 1001 1001 2002 2015 Then since 7 < 25 = 5 < 5 + 7, the final remainder is less than 1 and so the 2015000 2015000 − 2015 1000 floor is one less than 5 − 7 · 5 + · · · + 7 , and we calculate the remainder of the expression mod 1000. We can rewrite the expression as: 1000 ∑ 2015 i 1000 − i 5 · ( − 7) i =0 n 2015 i Then for n ≥ 2, we can see that 25 mod 1000 ≡ 625 mod 1000 and so 5 ≡ 125 mod 1000 for i odd and 625 for i > 0 even. So: 1000 500 ∑ ∑ 2016 i 1000 − i 1000 1000 − 2 i +1 1000 − 2 i 5 · ( − 7) ≡ 7 + 125 · ( − 7) + 625 · ( − 7) mod 1000 i =0 i =1 Then note that 125 · ( − 7) ≡ 125 mod 1000 and similarly 625 · ( − 7) ≡ 625 mod 1000. And hence: 1000 500 ∑ ∑ 2016 i 1000 − i 1000 1000 5 · ( − 7) ≡ 7 + (125 + 625) ≡ 7 mod 1000 i =0 i =1 6 1000 1000 This reduces to finding 7 mod 8 and 7 mod 125 and combining the two. It is clear 1000 ϕ (125) 100 1000 that 7 ≡ 1 mod 8 and by the Euler’s theorem, 7 = 7 ≡ 1 mod 125 so 7 ≡ 1 1000 mod 125. And so 7 ≡ 1 mod 1000. Now since the floor of the original expression is one less than this, we get that: ⌊ ⌋ 2017015 5 ≡ 0 mod 1000 2015 5 + 7 Author: Roy Zhao