Re: [中學] 2011AIME
※ 引述《rfdgrfdg (指考哥)》之銘言：
: 1.設x^3-2011x+m有整數根a,b,c 其中a>=b>=c 試求|a|+2|b|+|c|=?
: 2.設R是所有2^n除以1000的餘數所形成的集合，其中ｎ是非負整數，Ｓ是Ｒ中所有元素的和，試求Ｓ除以１０００的餘數
WLOG 假設 2^m 與 2^n (m>n)餘數相同
所以 2^m-2^n | 1000 想當於 2^n(2^(m-n)-1)|1000 = 8*125
顯然2^n 一定整除8 故只需考慮2^((m-n)-1)|125
令m-n=k 2^k-1|125
由餘數可知 k=4t (t屬於N) 代入後
(2^2t+1)(2^2t-1)|125
<=> (4^t+1)(2^t+1)(2^t-1)|125
有5的因數時 ↑ ↑ ↑
t=odd t=4p+2 t=4q
顯然不管t是什麼數，這三個因數只能有一個有5的因數
所以分三種情況討論
(1) (4^t+1)|125 t=2a+1(a為非負整數}) 代入
<=> (4^(2a+1)+1) |125
<=> (4+1)(4^2a-4^(2a-1)+4^(2a-2)....+1)
後者需整除25 觀察後可發現 2a=10b+4 (1{-4+16}+{-64+256}相當於1+2+2(mod5))
令a=5b+2代入(b為非負整數)
<=> (4^(10b+5)+1)|125 <=> (1024^(2b+1)+1)|125 <=> (24^(2b+1)+1) |125
<=> (24+1)(24^2b-24(2b-1)+24^(2b-2)....+1)|125
後者需整除5的最小b為2 → a=12→ t=25→ k=100
所以2^n(2^100-1)|1000 n>=3 所以每100個會重複 第一項是2^3跟2^103
即可計算 1+2+2^2+....+2^102 = 2^103-1 = 2^3-1 = 7
(2) (2^t+1)|125 t=4p+2 代入
<=> (4^(2p+1)+1)|125
<=> (4+1)(4^2p-4^(2p-1)+4^(2p-2)...+1)
可以發現跟(1)的情況一樣
最後會得出t=200 而由上述討論可知在t=100已經重複
(3) (2^t-1)|125
這個跟題目 第一步(2^m-2^n)|125
狀況一樣(陷入迴圈)
但顯然，繼續討論得到的t皆比100大
所以1+2+2^2+....+2^102 = 2^103-1 = 2^3-1 = 7
這題跟IMO考得一樣(連IMO那題也是差100會有同餘數)，不過這題轉了個彎就是了~
--
Like a million stardust
忘れないから 共に過ごした一瞬さえ全部
君の未来を僕は祈るよ
My precious one,but I keep going
For dearest...graffias is on the one -- バルシェ <story teller > graffias
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.113
※ 編輯: FAlin 來自: 140.112.240.113 (03/20 12:01)
推
03/21 21:18, , 1F
03/21 21:18, 1F
討論串 (同標題文章)