UVA 11582 Colossal Fibonacci Numbers：Pisano 周期 + 大整數模運算

數學核心

斐波那契數列模 n 必然週期（Pisano 周期），周期長度 ≤ n²。問題轉化為：
1. 求 F(k) mod n 的最小正周期 loop
2. 計算 a^b mod loop（大指數模運算）
3. 輸出 F(a^b mod loop) mod n

周期檢測

迭代生成 f[i] = (f[i-1]+f[i-2]) % n，當出現 f[i]==f[1] && f[i-1]==f[0] 時，周期 loop = i-1。上界 n*n+100 足夠安全（n ≤ 1000）。

大指數模運算

遞歸快速冪：pow_mod(a, b, mod)，處理 a,b ≤ 2^64 用 unsigned long long，中間乘積取模防溢出。

完整代碼

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 1000*1000 + 100;
ULL f[MAXN];

ULL pow_mod(ULL a, ULL p, ULL mod) {
    if(p==0) return 1;
    ULL half = pow_mod(a, p/2, mod);
    half = (half * half) % mod;
    if(p&1) half = (half * a) % mod;
    return half;
}

int main() {
    int T; cin >> T;
    while(T--) {
        ULL a,b; int n; cin >> a >> b >> n;
        f[0]=0; f[1]=1%n;
        int loop=1;
        for(int i=2;i<=n*n+100;++i) {
            f[i] = (f[i-1]+f[i-2]) % n;
            if(f[i]==f[1] && f[i-1]==f[0]) { loop=i-1; break; }
        }
        ULL idx = pow_mod(a % loop, b, loop);
        cout << f[idx] << endl;
    }
    return 0;
}

複雜度

預處理周期 O(n²)，單查詢 O(log b)，T ≤ 100，n ≤ 1000 完全足夠。