【题解】UVa P11582【Colossal Fibonacci Numbers!】

背景

Cinema开始学习数论了,这个题神烦,都交了20+次了。

分析

因为要模一个数,所以斐波那契数列会有循环节,然后我们显然发现,当任意两项与头两项重复时,整个序列就重复了,于是我们只需要求出循环节,再配合快速幂,即可达到目的。

代码

#include<cstdio>
#include<vector>
using std::vector;
typedef unsigned long long int64;
const int MAXN = 1008;
vector<int> fib;

int binaryPow(int64 a,int64 b,int p){
    int64 ans = 1;a %= p;
    while(b > 0){
        if(b & 1) ans = ans * a % p;
        b >>= 1;a = a * a % p;
    }
    return (int)ans;
}
void init(){
    for(int i = 0;i < 666666;i++) fib.push_back(0);
}

int main(){
    int64 a,b;int T,n,M;scanf("%d",&T);init();
    while(T--){
        scanf("%llu %llu %d",&a,&b,&n);
        if(n == 1 || a == 0){printf("0\n");return 0;}
        fib[0] = 0;fib[1] = 1;fib[2] = 1;
        for(int i = 3;i <= n * n;i++){
            fib[i] = (fib[i - 1] % n + fib[i - 2] % n) % n;
            if(fib[i] == fib[2] && fib[i - 1] == fib[1]){M = i - 2;break;}
        }
        printf("%d\n",fib[binaryPow(a % M,b,M)]);
        init();
    }

    return 0;
}