$f[n]\bmod q=p^{Fib[n]}\bmod q=p^{Fib[n]\bmod\varphi(q)}\bmod q$

首先線性篩預處理出所有素數，然后對于每次詢問，求出$\varphi(q)$，再用矩陣快速冪求出Fib[n]，最后用快速冪求答案即可。

?

#include<cstdio> typedef long long ll; const int N=46341; int T,i,j,p[N],tot,vis[N],n,q;ll a,P; struct mat{ll a[2][2];inline mat(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}inline mat operator*(mat b){mat c;for(int i=0,j,k;i<2;i++)for(j=0;j<2;j++)for(k=0;k<2;k++)(c.a[i][j]+=a[i][k]*b.a[k][j]%P)%=P;return c;} }A,B,C; inline int phi(int n){int t=1,i;for(i=1;p[i]*p[i]<=n&&i<=tot;i++)if(n%p[i]==0){n/=p[i],t*=p[i]-1;while(n%p[i]==0)n/=p[i],t*=p[i];}if(n>1)t*=n-1;return t; } inline int fib(int x){P=phi(q);for(A=B=C=mat(),A.a[0][1]=A.a[1][0]=A.a[1][1]=B.a[1][0]=C.a[0][0]=C.a[1][1]=1;x;x>>=1,A=A*A)if(x&1)C=C*A;C=C*B;return C.a[0][0]; } inline int pow(ll a,int b){ll t=1;for(;b;b>>=1,a=a*a%q)if(b&1)t=t*a%q;return t;} int main(){for(i=2;i<N;i++){if(!vis[i])p[++tot]=i;for(j=1;j<=tot;j++){if(i*p[j]>=N)break;vis[i*p[j]]=1;if(i%p[j]==0)break;}}scanf("%d%lld",&T,&a);while(T--){scanf("%d%d",&n,&q);if(q==1){puts("0");continue;}printf("%d\n",pow(a,fib(n)));}return 0; }

　　

?

轉載于:https://www.cnblogs.com/clrs97/p/4403141.html

總結

以上是生活随笔為你收集整理的BZOJ1409 : Password的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。