Re: [問題] 大數如何遞減?

看板C_and_CPP (C/C++)作者EdisonX (卡卡獸)時間13年前 (2013/01/22 09:00)推噓8(8推 0噓 18→)

留言26則, 9人參與討論串2/3 (看更多)

※ 引述《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, , 1^F

01/22 09:35, 1^F

→

EdisonX

01/22 09:56, , 2^F

01/22 09:56, 2^F

→

stimim

01/22 10:52, , 3^F

01/22 10:52, 3^F