国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > BZOJ 1409 Password 矩阵乘法+线性筛

BZOJ 1409 Password 矩阵乘法+线性筛

来源:程序员人生   发布时间:2015-03-25 11:36:42 阅读次数:2634次

题目大意:求p^F[n] mod q 其中F是斐波那契数列,p是质数,q<p

由于pq互质因此可以套用欧拉定理

然后就是矩乘求斐波那契的事情了- -

垃圾题卡O(√q) 求Phi的时候要枚举质数 不能1个1个枚举

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const long long empty[2][2]={{0,0},{0,0}}; const long long I[2][2]={{1,0},{0,1}}; const long long trans[2][2]={{0,1},{1,1}}; int n,p,q,mod; int prime[100100],tot; bool not_prime[100100]; namespace Matrix_Multiplication{ struct Matrix{ long long xx[2][2]; Matrix(const long long _[2][2]) { memcpy(xx,_,sizeof xx); } long long* operator [] (int x) { return xx[x]; } friend void operator *= (Matrix &x,Matrix y) { int i,j,k; Matrix z(empty); for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) (z[i][j]+=x[i][k]*y[k][j])%=mod; x=z; } }; Matrix Quick_Power(Matrix x,int y) { Matrix re(I); while(y) { if(y&1) re*=x; x*=x; y>>=1; } return re; } } void Linear_Shaker() { int i,j; for(i=2;i<=100000;i++) { if(!not_prime[i]) prime[++tot]=i; for(j=1;prime[j]*i<=100000;j++) { not_prime[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int Phi(int x) { int i,re=x; for(i=1;(long long)prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) { re/=prime[i];re*=prime[i]⑴; while(x%prime[i]==0) x/=prime[i]; } if(x!=1) re/=x,re*=x⑴; return re; } int Quick_Power(long long x,int y) { long long re=1; while(y) { if(y&1) (re*=x)%=q; (x*=x)%=q; y>>=1; } return re; } int main() { using namespace Matrix_Multiplication; int T; Linear_Shaker(); for(cin>>T>>p;T;T--) { scanf("%d%d",&n,&q); mod=Phi(q); int ans=Quick_Power(trans,n)[1][0]; printf("%d ",(int)Quick_Power(p,ans)%q); } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生