一個數學問題,一旦出現循環確定循環節以后就能解決問題啦.
加上一個快速冪取模.需要注意的是數據范圍是264,所以必須用unsigned long long才能解決問題.
覺得板子還是要會自己寫,否則不同的題目具體有一些小的改變就會束手無策.
還有就是發現如果每次初始化數組的話就會超時,所以需要注意在不必要 的時候或者可以通過簡單賦值的時候不要用memset進行初始化,挺耗時間.
看其他人為了避免超時進行打表,這也是一種思路.只是找到循環節需要多長的斐波那契數列理論上是n*n的,但是具體操作起來好像10 * n就可以找到.玄學.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
typedef unsigned long long ull;
const int INF=0x3f3f3f3f;
const int MAXN=1e3+15;int f[MAXN*MAXN];
ull a,b;
int n,x;
int len;void deal()
{memset(f,0,sizeof(f));f[0]=0%n; f[1]=1%n;int tmp=n*n;for(int i=2;i<=tmp+5;i++){f[i]=(f[i-1]+f[i-2])%n;if(f[i-1]==f[0] && f[i]==f[1]){len=i-1;break;}}
}ull quick_pow(ull a,ull b,ull len)
{ull ret=1;a=a%len;while(b){if(b&1) ret=a%len*ret%len;b>>=1;a=a*a%len;}return ret;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%llu%llu%d",&a,&b,&n);if(a==0 || n==1){printf("0\n");continue;}deal();x=(int)quick_pow(a,b,len);printf("%d\n",f[x]);}return 0;
}
)
