e613 - 13216 - Problem with a ridiculously long name but with a ridiculously short description
題目描述
題目要求計算 66 的 n 次方模 100 的結果，其中 n 的範圍很大 (1 ≤ n ≤ 10^1000)。
解題思路
觀察 66 的 n 次方模 100 的結果，可以發現其具有週期性。
- 66^1 mod 100 = 66
- 66^2 mod 100 = 36
- 66^3 mod 100 = 96
- 66^4 mod 100 = 56
- 66^5 mod 100 = 76
- 66^6 mod 100 = 16
- 66^7 mod 100 = 36 ... 週期為 6。因此，只需要計算 n mod 6 的值，然後根據結果輸出對應的答案即可。 當 n = 1 時，答案為 1。 當 n 的最後一位是 0 或 5 時，答案為 76。 當 n 的最後一位是 1 或 6 時，答案為 16。 當 n 的最後一位是 2 或 7 時，答案為 56。 當 n 的最後一位是 3 或 8 時，答案為 96。 當 n 的最後一位是 4 或 9 時，答案為 36。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
string a;
cin >> n;
while(n--){
cin >> a;
int al=a.length();
if(al==1){
int b=a[0]-48,ans=1;
while(b--){
ans*=66;
ans%=100;
}
cout << ans << "\n";
}
else if(a[al-1]=='0'||a[al-1]=='5')
cout << "76\n";
else if(a[al-1]=='1'||a[al-1]=='6')
cout << "16\n";
else if(a[al-1]=='2'||a[al-1]=='7')
cout << "56\n";
else if(a[al-1]=='3'||a[al-1]=='8')
cout << "96\n";
else
cout << "36\n";
}
}