斐波那契数是很多人众所周知的了，那么如果叫你算18446744073709551615×18446744073709551615 mod 1000的斐波那契数，你是否有快速的方法进行计算呢，这就是我们今天要讨论的问题，首先让我们来看题目吧

题目传送门

题意

题意非常简单，就是给你一个a，b，n，让你算出斐波那契数列的第a^b项，然后该项的数值对n取模，输出即可。只不过a和b的范围都非常大，达到了2^64。

斐波那契循环节

我们看到a和b的范围就知道肯定不能傻乎乎地使用常规的方法去做了，首先一点我们可以确定的是这个题目最终的答案一定不会大于n（因为对n取模），所以我们会思考是不是会有一种周期性的循环可以让我们无需耗费大量时间去计算斐波那契（我一开始就是这么个想法，毕竟时间限制1000ms，肯定使用了某种周期的性质），这时候，最好的方法就是自己动手去寻找规律了！（数论的题目建议最好都在纸上模拟一下找一下规律，还不会占用电脑哈哈）。

我们先写出n=2时前十个斐波那契数列（从1开始）：1,1,0,1,1,0,1,1,0,1。除去最后一个1，我们发现确实好像有循环。一次不够我们再枚举n=3:1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0。。。。我们也可以发现斐波那契数列开始循环了，那么原因在哪里呢？

其实是这样的，我们可以看到取模过的斐波那契数列，仍然会保留f[n]=f[n-1]+f[n-2]的规律，那么如果我们在某一时刻f[n-1]==f[1],f[n-2]==f[2],那么自然会产生f[n]==f[3]和后面的所有规律，那么我们只要计算一次这样的循环就可以了，后面的所有的项直接对于这个循环的长度进行取模就可以了。

取模快速幂

然后我们就要解决快速幂的问题了，我们不可能让两个2^64的数字直接相乘，所以我们得一边使用快速幂一边进行取模，然后就可以解决问题了
取模快速幂代码：

ull pow_mod(ull a,ull i,int n){
    if(i==0)
        return 1%n;
    ull t=pow_mod(a,i>>1,n);
    t=t*t%n;
    if(i&1)
        t=t*a%n;
    return t;
 }

代码

全部代码如下：

#include <iostream>
#include <cmath>
using namespace std;
const int N=1010;
typedef unsigned long long ull;

int fib[N*N];

ull pow_mod(ull a,ull i,int n){
    if(i==0)
        return 1%n;
    ull t=pow_mod(a,i>>1,n);
    t=t*t%n;
    if(i&1)
        t=t*a%n;
    return t;
 }

void cal(int& n){
    fib[0]=0;
    fib[1]=fib[2]=1;
    for(int i=3;i<=n*n+1;i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % n;
        if(fib[i]==fib[2]&&fib[i-1]==fib[1]){
            n=i-2;
            break;
        }
    }
}

int main(){
    int n,T;
    ull a,b;
    while(cin>>T){
        while(T--){
            cin>>a>>b>>n;
            if(n==1||!a)
                cout << 0 << endl;
            else {
                cal(n);
                ull sum = pow_mod(a % n, b, n);
                cout << fib[sum] << endl;
            }
        }
    }
    return 0;
}

In The End

UVA11582题：巨大的斐波那契数（斐波那契循环节+取模快速幂）

题目传送门

题意

斐波那契循环节

取模快速幂

代码