› 看板 Just_a_name 關於我們 聯絡資訊
作者thisday (小綱)
看板Just_a_name
標題Re: [秩綱] 請教你一題數學
時間Fri Apr 9 17:40:22 2010
─────────────────────────────────────── 想法 : 先知道 90!最後面有幾個零 [90/5]+[90/25]=21 => 5^21｜90! ∴有21個0 我們考慮90!= k*2^21*5^21 (k,25)=1 如此一來 k 的末兩位數字即為所求 ____________________________________________________________________________ 我用≒表示把5的次方拿掉再mod 25的餘數 [90/5]+[90/25]=21 => 5^21｜90! 因 (5k+1)(5k+2)(5k+3)(5k+4)≡-1 (mod 25) 又90=5*18, 18=5*3+3 故90!≒(-1)^18*18!≒18!≒(-1)^3*16*17*18*3!≒-1 90!中共有18組型如:(5k+1)(5k+2)(5k+3)(5k+4)的相乘數字 剩下的5 10 15 20...85 90 將5去除後得到18! ∴ k*2^21=-1 (mod 25) 至此已經把5^21都去除掉了 再來把2^21去除掉 => 90!*2^(-21)≒-1*2^(-21) ————————————————————— ≒-1*13^21 ∣ ∵ 2*13=26=1 (mod 25) ∣ => 2^(-1)=13 (mod 25) ∣ => 2^(-21)=13^21 (mod 25) ————————————————————— ≒-1*13≒12 ∣ 由歐拉定理φ(25)=25(1-1/5)=20 ∣ ∴ 13^20= 1(mod 25) ∣ => 13^21=13(mod 25) ————————————————————— 由上知 k=12 (mod 25) ∣ 因此我們可以知道 k 的末兩位數 ∣ 可能為12,37,62,87 又 2^23｜90! 亦即 4｜k ————————————————————— ∴ k=12 (mod 100) 故 90! 從右到左首二位不為零的數字為12 維基上的 同餘 http://tinyurl.com/y79h24f 歐拉函數 http://tinyurl.com/y5hy6m3 歐拉定理 http://tinyurl.com/y6t7uth -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.242.18
→ thisday:自己想了一個小時,找類似題目找了兩個小時 04/09 17:41
→ thisday:看懂別人的算法花一個小時 04/09 17:42
※ 編輯: thisday 來自: 140.112.242.18 (04/09 17:44)
推 nancy5431:大大感謝 那麼以我的理解力..我會花上 8 個小時來研究 04/10 00:12
推 nancy5431:真正強者! 謝謝你 >////< 04/10 00:12
推 nancy5431:借我轉去高中板和我的老師分享噢~ 再感謝一次 04/10 00:15
→ Marsoctopus:太驚恐了，這什麼東西？ 04/10 18:21
推 nancy5431:我的老師說非常謝謝你 :) 說你的解法很不錯!! 謝謝囉! 04/10 23:16