d271 - 11582 - Colossal Fibonacci Numbers!
題目描述
題目要求計算費氏數列的第 a^b 項模 n 的結果。由於 a^b 可能非常大，直接計算費氏數列是不現實的。因此，需要利用費氏數列的週期性來解決問題。
解題思路
核心思想是利用費氏數列模 n 的週期性。費氏數列模 n 必定存在一個週期，即存在一個 k 使得 F(i + k) ≡ F(i) (mod n) 對所有 i 成立。
程式碼首先計算費氏數列模 n 的週期。然後，計算 a^b mod k，最後根據這個值來確定費氏數列中的哪個項，並輸出該項模 n 的結果。
程式碼中 mod 函數實現了快速冪運算，用於計算 a^b mod k。主迴圈中，計算費氏數列模 n 的值，直到找到週期。a[it++]=f; 儲存了費氏數列模 n 的值，用於後續的查詢。
複雜度分析
- 時間複雜度: O(n^2 + log b) 其中 n 是模數，log b 是快速冪的複雜度。計算週期最壞情況下需要 O(n^2)，快速冪是 O(log b)。
- 空間複雜度: O(n) 用於儲存費氏數列模 n 的值。
程式碼
#include <iostream>
using namespace std;
unsigned long long n,x,y,z,a[1000005];
unsigned long long mod(unsigned long long xx,unsigned long long yy,unsigned long long mm){
if(xx==1)return 1;
if(yy==0)return 1;
if(yy==1)return xx;
unsigned long long tmp=mod(xx,yy/2,mm)%mm;
if(yy%2){
return (tmp*tmp)%mm*xx%mm;
}
else{
return (tmp*tmp)%mm;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int ca=0;ca<n;++ca){
cin >> x >> y >> z;
if(z==1){
cout << "0\n";
}
else{
unsigned long long f=1%z,la=0,tmp=0,it=1;
while(f!=1||la!=0||it==1){
a[it++]=f;
tmp=f;
f+=la;
la=tmp;
f%=z;
}
--it;
cout << a[mod(x%it,y,it)] << "\n";
}
}
}