e553 - 10162 - Last Digit
題目描述
題目要求計算 S = 1^1 + 2^2 + 3^3 + ... + N^N 的最後一位數字。輸入為多個整數 N，直到輸入為 0 時結束。
解題思路
由於只需要計算最後一位數字，我們可以只考慮每個數的個位數。觀察 N^N 的個位數變化，可以發現存在週期性。程式碼預先計算了 0 到 100 的每個數字的 N^N 的最後一位數字，並儲存在 ans 陣列中。對於輸入的 N，如果 N 小於等於 100，直接從 ans 陣列中讀取結果。如果 N 大於 100，則利用個位數和十位數的組合來索引 ans 陣列，因為 N^N 的最後一位數字只取決於 N 的最後兩位數字。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int ans[101],tmp;
string a;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=0;i<=100;++i){
int it=i%10;
if(it==2||it==8)
(i%4==2)?tmp+=4:tmp+=6;
else if(it==3||it==7)
(i%4==3)?tmp+=10-it:tmp+=it;
else if(it==4)
tmp+=6;
else
tmp+=it;
tmp%=10;
ans[i]=tmp;
}
while(cin >> a){
if(a=="0")break;
int p=a[a.length()-1]-48;
if(a.length()<=1)cout << ans[p] << "\n";
else cout << ans[(a[a.length()-2]-48)*10+p] << "\n";
}
}