UVA - 11582 Colossal Fibonacci Numbers!（找循环节）
题目链接
首先紫书上描述有误， f ( 0 ) = 0 , f ( 1 ) = 1 f(0)=0,f(1)=1 f(0)=0,f(1)=1
关于循环节的最大寻找长度，紫书上解释说余数最多 n n n种，那么最多 n 2 n^2 n2项就会出现重复。我一开始觉得这是一个组合数学的问题，但是想了想觉得中间有递推关系，严格的证明不会。但是数学规律题一般都能取巧的，我们可以把 n n n取 1 − 1000 1-1000 1−1000所有的周期打个表，然后找下最大的即可
吐槽下此题玄学RE，2e6也RE，搞吐了
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1007;
int f[maxn*maxn];
int m;
void init(int n){
f[0]=0,f[1]=1%n;
for(int i=2;i<n*n+10;i++){
f[i]=(f[i-1]+f[i-2])%n;
if(f[i-1]==f[0] && f[i]==f[1]){
m=i-1;
break;
}
}
}
ull quick_pow(ull x,ull n,int p){
ull ans=1;
while(n){
if(n&1) ans=ans*x%p;
x=x*x%p; //如果不传入x%m这里会溢出
n>>=1;
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t,n;
ull a,b;
cin>>t;
while(t--){
cin>>a>>b>>n;
init(n);
cout<<f[quick_pow(a%m,b,m)]<<endl;
}
return 0;
}