d361 - 10515 - Power et al.
題目描述
題目要求計算 m^n 的個位數字。輸入為兩個非負整數 m 和 n，輸出 m^n 的個位數字。當 m 和 n 都為 0 時，程式結束。
解題思路
由於只需要計算個位數字，因此可以利用同餘的概念，只考慮個位數的運算。觀察不同個位數 m 的冪的個位數變化規律，可以發現它們會呈現週期性的循環。程式碼中，針對不同的個位數 m (0-9)，分別計算 m^n 的個位數。對於 m 的個位數為 2, 3, 7, 8 的情況，需要考慮 n 的值，因為它們的循環週期較長，需要取 n 對 4 的餘數來確定個位數。對於 m 的個位數為 4 和 9 的情況，只需要考慮 n 的奇偶性來確定個位數。其他情況則直接輸出 m 的個位數即可。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
string a,b;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> a >> b){
if(a=="0"&&b=="0")break;
int n=a[a.length()-1]-48;
if(a=="0")
cout << "0\n";
else if(b=="0")
cout << "1\n";
else if(n==0||n==5||n==6||n==1)
cout << n << "\n";
else if(n==2){
int bl=b.length(),k;
if(bl>=2)
k=((b[bl-1]-48)+10*(b[bl-2]-48))%4;
else
k=(b[bl-1]-48)%4;
if(k==0)
cout << "6\n";
else if(k==1)
cout << "2\n";
else if(k==2)
cout << "4\n";
else
cout << "8\n";
}
else if(n==3){
int bl=b.length(),k;
if(bl>=2)
k=((b[bl-1]-48)+10*(b[bl-2]-48))%4;
else
k=(b[bl-1]-48)%4;
if(k==0)
cout << "1\n";
else if(k==1)
cout << "3\n";
else if(k==2)
cout << "9\n";
else
cout << "7\n";
}
else if(n==4){
int bk=(b[b.length()-1]-48)%2;
if(bk)
cout << "4\n";
else
cout << "6\n";
}
else if(n==7){
int bl=b.length(),k;
if(bl>=2)
k=((b[bl-1]-48)+10*(b[bl-2]-48))%4;
else
k=(b[bl-1]-48)%4;
if(k==0)
cout << "1\n";
else if(k==1)
cout << "7\n";
else if(k==2)
cout << "9\n";
else
cout << "3\n";
}
else if(n==8){
int bl=b.length(),k;
if(bl>=2)
k=((b[bl-1]-48)+10*(b[bl-2]-48))%4;
else
k=(b[bl-1]-48)%4;
if(k==0)
cout << "6\n";
else if(k==1)
cout << "8\n";
else if(k==2)
cout << "4\n";
else
cout << "2\n";
}
else if(n==9){
int bk=(b[b.length()-1]-48)%2;
if(bk)
cout << "9\n";
else
cout << "1\n";
}
}
}