问题 A: Password
时间限制: 1 Sec 内存限制: 64 M题目描述
Rivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]}，
且E[1] = E[2] = p（p为一个质数），E[i] = E[i-2]*E[i-1] （若2<i<=n）。
例如{2,2,4,8,32,256,8192,……}就是p = 2的数列。在此基础上他又设计了一种加密算法，该算法可以通过一个密钥q (q < p)将一个正整数n加密成另外一个正整数d，计算公式为：d = E[n] mod q。现在Rivest想对一组数据进行加密，但他对程序设计不太感兴趣，请你帮助他设计一个数据加密程序。
输入
第一行读入m，p。其中m表示数据个数，p用来生成数列E。 以下有m行，每行有2个整数n，q。n为待加密数据，q为密钥。 数据范围: 0 < p n< 2^31 0 < q < p 0 < m <= 5000。
输出
将加密后的数据按顺序输出到文件 第i行输出第i个加密后的数据。 输入样例1 2 7 4 5 4 6 输入样例2 4 7 2 4 7 1 6 5 9 3
样例输入
输入样例1
2 7
4 5
4 6
输入样例2
4 7
2 4
7 1
6 5
9 3
样例输出
输出样例1
3
1
输出样例2
3
0
1
1
p的多少次幂显然是一个斐波那契数列，考虑用矩阵快速幂，但会炸ll，
欧拉函数扩展 p^phi(q)%q=1，这样，求出phi(q)，乘的时候%一下。
求出p^f[n]后，再用普通快速幂求出ans即可
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long using namespace std; ll m,p,n,q,pp,inf=(1<<31)-1,phi[46400],mark[46400],tot,prime[40000]; ll k; struct node { ll f[2][2]; node(){ memset(f,0,sizeof(f)); } } a,b; ll read() { ll sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar(); return sum*f; } void get_phi() { phi[1]=1; for(ll i=2;i<=sqrt(inf);i++) { if(!mark[i]) { prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot;j++) { if(i*prime[j]>sqrt(inf))break; mark[i*prime[j]]=1; if(!(i%prime[j])) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } ll pphi(ll x) { ll t=x; for(ll i=1;prime[i]*prime[i]<=t;i++) if(!(x%prime[i])) { t=t-t/prime[i]; while(!(x%prime[i])) x/=prime[i]; } if(x>1) t=t-t/x; return t; } node cheng(node a,node b) { node c; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { for(int l=0;l<2;l++) { c.f[i][j]+=a.f[i][l]*b.f[l][j]; c.f[i][j]%=k; } } return c; } int main() { //freopen("password.in","r",stdin); //freopen("password.out","w",stdout); m=read();p=read(); get_phi(); while(m--) { n=read();q=read();pp=p; if(q>sqrt(inf)) k=pphi(q); else k=phi[q]; a.f[0][0]=0;a.f[1][0]=1;a.f[1][1]=0;a.f[0][1]=0; b.f[0][0]=1;b.f[0][1]=1;b.f[1][0]=1;b.f[1][1]=0; node s; for(int i=0;i<2;i++) for(int j=0;j<2;j++) s.f[i][j]=(i==j); while(n) { if(n&1)s=cheng(b,s); b=cheng(b,b); n/=2; } s=cheng(s,a); n=s.f[0][0]; ll ans=1; while(n) { if(n&1)ans=(ans*pp)%q; pp=(pp*pp)%q; n/=2; } printf("%lld ",ans%q); } }