切換
舊版
前往
大廳
主題

ZeroJudge - e553: 10162 - Last Digit　解題心得

Not In My Back Yard | 2019-12-06 15:28:39 | 巴幣 2 | 人氣 433
題目連結：
題目大意：
給定一正整數 N （1 ≦ N ≦ 2 × 10 ^ 100，N ＝ 0 時代表輸入結束），求 1 ^ 1 ＋ 2 ^ 2 ＋ 3 ^ 3 ＋ …… ＋ N ^ N 的最後一位數為多少？

範例輸入：
1
2
3
0
範例輸出：
1
5
2
解題思維：
觀察 2 結尾數字次方：2 ^ 2 → 4 、12 ^ 12 → 6  、22 ^ 22 → 4  、32 ^ 32 → 6 、 ……可以看到其以 4 、 6 作為循環節。

同樣地，結尾為 0 、 1 、 3 、 4 、 5 、 6 、 7 、 8 、 9 各自的循環節為：
{ 0 } 、 { 1 } 、 { 7、3 } 、 { 6 } 、 { 5 } 、 { 6 } 、 { 3 、 7 } 、 { 6 、 4 } 、 { 9 }

接著，我們可以看到 1 ^ 1 ＋ 2 ^ 2 ＋ 3 ^ 3 ＋ …… ＋ 99 ^ 99 的結尾（用上面的循環節可得出每跑過一次 0 ～ 9 ，尾數就會 ＋ 7）為 0。

而 101 ^ 101 ＋ 102 ^ 102 ＋ …… ＋ 999 ^ 999 尾數與上式等價，也同樣是 0 。其他也以此類推。

由上可知，我們可以直接取 N 的末兩位。接著，因為數字範圍（以下稱此數為 M）已被縮減到 100 以內，所以想要直接乘並總和出結果（運算過程要記得一直取 10 的餘數）是可以的。但是既然有了上面循環節的表，便可以善加利用。

將 M 寫為 D × 10 ＋ C（其中，0 ≦ C ≦ 9）。而 D 代表已經經過了多少次的尾數 ＋ 7 （緣由看循環節的部分）。

因此尾數為 D × 7 ＋ （10D（含） ～ 10D ＋ C（含）這 C ＋ 1 個數各自的尾數之相加）取 10 的餘數即是所求。而 10D ～ 10D ＋ C 求尾數的部分用上面循環節的對照表即可得出。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#數論
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

妖魔鬼怪降伏於我

看更多

相關創作

鳥鳥玩數學-有趣的擲骰子機率問題(2022 大阪大學前期)
0 192
鳥鳥玩數學-高斯符號找質因數個數及原理(2020-2021 Hồ Chí Minh，Vietnam)
1 291
鳥鳥玩數學-平方差整數解之小技巧
1 263
鳥鳥玩數學-2022年考生要注意的事
0 305
鳥鳥玩數學-分母為相異質數不定方程(2016 越南數學選拔)
1 249
鳥鳥玩數學-對數與數論結合方程組問題(2019 AIME I)
0 317
鳥鳥玩數學-1000! 1000!! 999!! 找質因數個數(2018大阪市立大學)
0 206
鳥鳥玩數學-經典數論名題133^5+110^5+84^5+27^5=n^5 (1989 AIME)
0 293
鳥鳥玩數學-解 2^x+2^y+2^z=2336 (1982 Vietnam Mathematical Olympic)
0 224
鳥鳥玩數學-數論與平面座標的結合(2020 北海道大學 前期)
0 170
鳥鳥玩數學 三角函數與對數的結合(2019 京都大學前期)
0 253
鳥鳥玩數學-為兩年後準備，sqrt(a)+sqrt(b)=2023 正整數解
1 312
鳥玩數學-與2015互質，第2015個數(104高雄市聯招)
0 213
鳥鳥玩數學-證明sin1 cos1 tan1為無理數
0 297
鳥鳥玩數學-餘弦定理意想不到的用法，質數與餘弦定理的組合
0 270
鳥鳥玩數學-什麼!! n個相異自然數和等於n個相異自然數積只有一組解(1977 岐阜大學)
0 167
達人 《憂國的莫里亞蒂》中的數學公式
68 3178
cf #460 (Div. 2) pE Congruence Equation
0 140

更多創作

追蹤 創作集
其他創作
作品資料夾