思路：

1.\(f[i]%n\)具有周期性，找循环节即可
2.数据范围很大，要用ull

代码：

ll ksm_u(ull a, ull b, ll p)
{
    ll res = 1;
    a%=p;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
const int inf = 0x3f3f3f3f;
#define PI acos(-1)
const double eps = 1e-8;
const int maxn=1e6+7;
ll dp[maxn];
void solve(){
    ull a,b;
	cin>>a>>b;
	ll n=read;
	if(a==0||n==1){
		puts("0");return ;
	}
	dp[0]=0,dp[1]=1;
	int i=2,len;
	while(1){
		dp[i]=(dp[i-1]+dp[i-2])%n;
		if(dp[i]==1&&dp[i-1]==0){
			len=i-1;break;
		}
		i++;
	}
	ll tmp=ksm_u(a,b,len);
	cout<<dp[tmp]<<endl;
}

Colossal Fibonacci Numbers!（斐波那契+循环节）

原文：https://www.cnblogs.com/OvOq/p/14801921.html