作者EdisonX (卡卡獸)
看板C_and_CPP
標題Re: [問題] 大數如何遞減?
時間Tue Jan 22 09:00:28 2013
※ 引述《luke90512 (阿神)》之銘言：
: input為一系列的整數，範圍是1~2*10^100
: 對每個input假設為n
: 計算s=1^1+2^2+3^3+...+n^n
: 只取s的個位數作為答案
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: http://ideone.com/BQz0Uz
其他恕刪，我看你後來改的 code 還是有用到 pow 函式 (恕我沒細看理解)，
然後早上起床想了一下，做了一點推導可以參考一下。
數學表達不好，見諒，另我也不保證這想法是可 AC 的。
---
首先在意的是 1^1, 11^11, 21^21 尾數是多少；
再來在意的是 2^2, 12^12, 22^22 尾數是多少；
然後發現其實有規律可詢，
像 2^2 尾數是 4 ; 12^12 尾數是 6； 22^22 尾數是 4 ；32^32 尾數是 6... ；
依此類推，經過一點推導後結論如下 (可能有推錯，不過目前驗證是對的)
---
n/10=even, n=10=odd, n/10=even
-----------------------------
0 : 尾數必為 0 (0^0= 0, 10^10=..0, 20^20=..0)
1 : 尾數必為 1 (1^1= 1, 11^11=..1, 21^21=..1)
2 : 尾數變化
4 ->
6 -> 4 -> 6 -> ... (2^2=
4, 12^12=..
6, 22^22=..4)
3 : 尾數變數
7 ->
3 -> 7 -> 3 -> ... (3^3=..
7, 13^13=..
3, 23^23=..7)
4 : 尾數必為 6 (4^4=..6, 14^14=..6, 24^24=..6)
5 : 尾數必為 5 (5^5= 5, 15^15=..5, 25^25=..5)
6 : 尾數必為 6 (6^6= 6, 16^16=..6, 26^26=..6)
7 : 尾數變化
3 ->
7 -> 3 -> 7 -> .... (7^7=..
3, 17^17=..
7, 27^27=..3)
8 : 尾數變化
6 ->
4 -> 6 -> 4 -> .... (8^8=..
6, 18^18=..
4, 28^28=..6)
9 : 尾數必為 9 (9^9=..9, 19^19=..9, 29^29=..9)
---
上面如果會看的話，可以做很多事了，拿簡單的例子來講，
如果是算 1^1 + .... + 10^10 ，取變化的第一個數字 (像2的話就是
4，3的話是
7)
1^1 + .... + 10^10 = 1 +
4 +
7 + 6 + 5 + 6 +
3 +
6 + 9 + 0= 47，尾數=7
然後注意到，其實 10^10 有沒有加是無所謂、不影響結果的。
如果是算 11^11 + .... + 20^20 ，取變化的第二個數字 ( 2的話取
6，3的話取
3)
11^11 + .... + 20^20 = 1 +
6 +
3 + 6 + 5 + 6 +
7 +
4 + 9 + 0 = 47，尾數=7
再推廣下去的話，會變成，
1+.....+10^10 -> 47 ---> 尾數 7
1+.....+20^20 = (1+....+10^10) + (11^11 +....+20^20) -> (7 + 7) = 14 -> 尾數 4
1+.....+30^30 -> 7+7+7 = 21 --> 1
1+.....+40^40 -> 7*4 = 28 --> 8
1+.....+50^50 -> 7*5 = 35 --> 5
換句話說，如果 n 是 10 的倍數，或是10的倍數減 1，
那尾數就變成了..
( (n+1) / 10 ) * 7 % 10
然後接下來的剩下不是 n 的部份怎麼做呢？回到最上面一開始給你的規則，
去建表相加。
------------
再來是，上面的 1+....+10^10 , 1+....+20^20，是以 10 為 gap ，但其實有更好的
規則，是 gap 一次考慮 20 個，你會發現如下
1+....+20^20 ---> 尾數 = 4
1+....+40^40 ---> 尾數 = 8
1+....+80^80 ---> 尾數 = 2
1+....+100^100 ---> 尾數 = 0
1+....+120^120 ---> 尾數 = 4 ----> 這裡開始循環
8
2
0
...
上面這些可以建表。
有些超過題目太多就不說了，假設題目是給你 1+...+88^88 的話...
(1) 1+...+80^80 --> 尾數 = 2
< 從 n gap 20 規則取得, O(1) >
(2) 81^81 + ....+ 88^88 ，從最一開始給你的規則判斷，
---> 1 +
4 +
7 + 6 + 5 + 6 +
3 +
6 = 38 --> 尾數 = 8
最後得到 2+8 = 10，10%10 = 0, 這就是結果了。
在第二步要加快速度的話我會建立一個表，大概長這樣
int times_20[] = {0,1,4,7,6,5,6,3,6,9, // 00~09, 20~29, 40~49 尾數
0,1,6,3,6,5,6,7,4,9}; // 10~19, 30~39, 50~59 尾數
int column_times[20];
column_times[0] = times_20[0];
for(i=1; i<20; ++i)
column_times[i] = column_times[i-1] + times_20[i];
上面的 column_times 事先算好，然後第二步就可以就可用 column_times 去做，
O(1)，
於是整體的效能反而落在，大數(n) 除以 整數(20) / 大數(n) Mod 整數 (20)，
上面的 除以20 和 Mod20，是同一個副函式可做出來的東西。
---
這可能不是最快的，
implement 沒太大興趣，希望有給您一點靈感。
--
~ 這輩子與神手無緣
我只好當神獸了 ~
卡卡獸
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
推 hichcock:讚...程式只是工具, 重點是你怎麼解問題 01/22 09:35
→ EdisonX:想了一下,最後的 /20 , %20 還有機會偷工,不過我懶了 XD 01/22 09:56
→ stimim:也可以先算 1^1+...+n^n % 5 還有 1^1+...+n^n%2 再用 CRT 01/22 10:52
→ stimim:(i^i)%2 是兩個一循環，(i^i)%5 是 20 個一循環 01/22 10:56
→ EdisonX:s 大方法漂亮, 不過「算落在哪個循環」似乎還是要大數除 ? 01/22 11:08
→ suhorng:20個一循環 所以100個也會循環 吧？ 01/22 11:36
→ suhorng:(i^i)%5 可以從 (i^(i%4))%5 來看 大概是 20 的由來？ 01/22 11:37
推 stimim:n%20 應該不能算是大數除吧 XD ，只要看最後兩位就好了 01/22 11:42
→ EdisonX:熊熊腦鈍, 確實拿最後兩位數, 配合 CRT 就出來了, 謝謝 :) 01/22 11:57
推 luke90512:感謝Ed大還有各位~ 看來頭腦要再靈活一點了! 01/22 12:29
推 ericinttu:推一下, 我還沒想到底. 01/22 13:52
推 damody:推e大 推人超好~ 01/22 13:54
推 luke90512:請問一下CRT是什麼呢? 01/22 15:53
→ suhorng:chinese remainder theorem 01/22 16:03
→ stimim:中國剩餘定理 01/22 16:03
→ Donze:((n-1)/10)*7%10 那邊應該是n+1 因為19^19跟20^20的結果一樣 01/22 17:41
→ Donze:然後一次考慮20個那邊第一行應該是 1+....+20^20才對 01/22 17:42
謝謝 D 大指正 :)
※ 編輯: EdisonX 來自: 180.177.76.161 (01/22 17:57)
推 FrankWOO:sum(i^i)的個位數每180個一循環，所以只要算(i^i)%180 01/22 18:09
→ Donze:有人可以解釋一下推文的循環都怎麼出來的嗎? 01/22 18:40
→ EdisonX:(i^i)%180,這個要配大數的話大概沒辦法吧? 10^n/180 不會 01/22 18:59
→ EdisonX:是整數吧 01/22 19:01
推 stimim:費馬小定理 x^(p-1)%p=1 若p是質數，所以i^i%5=i^(i%4)%5 01/22 19:04
→ stimim:所以最多 5*4 個就會循環 01/22 19:05
→ stimim:而 (1^1+...+n^n)%5 最多只要再 5 倍，也就是 100 個一循環 01/22 19:05
→ EdisonX:< 小聲的說,數學不好其實可以先寫一份簡易大數,用暴力觀查 01/22 19:05
→ EdisonX: 多暴力呢？ 就和 分數化循環小數 不用數學解 一樣暴力 > 01/22 19:06