思路是按紫书上说的来。
参考了:https://blog.csdn.net/qwsin/article/details/51834161 的代码；
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
const int MAXN=+; ll a, b;
int n,M;
int f[MAXN*MAXN]; int pow_mod(ll p, ll q, int Mod)
{
if(!q) return ;
int x = pow_mod(p, q/, Mod);
int ans = x*x % Mod;
if(q%)
ans = ans*p % Mod;
return ans;
} void solve()
{
cin>>a>>b>>n;
if(n== || a==)
{
printf("0\n");
return ;
}
f[]=; f[]=;
int t=n*n;
for(int i=; i<=t+; i++)
{
f[i]=(f[i-]+f[i-])%n;
if(f[i]==f[] && f[i-]==f[])
{
M=i-;
break;
}
}
int k = pow_mod(a%M, b, M);
cout<<f[k]<<endl; } int main()
{
int T;
cin>>T;
while(T--)
solve(); return ;
}
代码中的ll改成ull比较合适。
注意第30行的初始值，我因为f[0]=1 卡了好几个小时。
另一种是LRJ的代码，为了方便大家看，我直接copy过来了。
// UVa11582 Colossal Fibonacci Numbers!
// Rujia Liu
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; const int maxn = + ;
typedef unsigned long long ULL; int f[maxn][maxn*], period[maxn]; int pow_mod(ULL a, ULL b, int n) {
if(!b) return ;
int k = pow_mod(a, b/, n);
k = k * k % n;
if(b % ) k = k * a % n;
return k;
} int solve(ULL a, ULL b, int n) {
if(a == || n == ) return ; // attention!
int p = pow_mod(a % period[n], b, period[n]);
return f[n][p];
} int main() {
for(int n = ; n <= ; n++) {
f[n][] = ; f[n][] = ;
for(int i = ; ; i++) {
f[n][i] = (f[n][i-] + f[n][i-]) % n;
if(f[n][i-] == && f[n][i] == ) {
period[n] = i - ;
break;
}
}
}
ULL a, b;
int n, T;
cin >> T;
while(T--) {
cin >> a >> b >> n;
cout << solve(a, b, n) << "\n";
}
return ;
}
其实大体上差不多，不过LRJ的关键代码是用二维数组，全部先列举出来。