[bzoj 1409] Password 矩阵快速幂+欧拉函数

考试的时候想到了矩阵快速幂+快速幂，但是忘（bu）了（hui）欧拉定理。

然后gg了35分。

题目显而易见，让求一个数的幂，幂是斐波那契数列里的一项，考虑到斐波那契也很大，所以我们就需要欧拉定理了

p是素数，所以可以搞 

然后我们用矩阵快速幂求出幂，然后快速幂即可解决问题

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;#define pos(i,a,b) for(int i=(a);i<=(b);i++)#define Ma 50000#define LL long longLL prime[Ma],num_prime;LL isnotprime[Ma]={1,1};LL c,ou;LL m,p,n,q;struct matrix{    LL a[10][10];    matrix(){        memset(a,0,sizeof(a));    }};matrix mul(matrix aa,matrix b){    matrix c;    pos(i,0,1){        pos(j,0,1){            c.a[i][j]=0;            pos(k,0,1){                c.a[i][j]=(c.a[i][j]+aa.a[i][k]*b.a[k][j])%ou;            }        }    }    return c;}void getprime(){    pos(i,2,Ma-1){        if(!isnotprime[i]){            prime[num_prime++]=i;        }        for(int j=0;j<num_prime&&i*prime[j]<Ma;j++){            isnotprime[i*prime[j]]=1;            if(!(i%prime[j])){                c++;                break;            }        }    }}matrix init(){    matrix res;    pos(i,0,1){        pos(j,0,1)            res.a[i][j]=(i==j);    }    return res;}matrix ks(matrix aa,int k){    matrix res=init();    while(k){        if(k&1)          res=mul(res,aa);        k>>=1;        aa=mul(aa,aa);    }    return res;}LL oula(LL nn){    LL mm=(int)sqrt(nn+0.5);    LL an=nn;    for(int i=0;prime[i]<=mm;i++){        if(nn%prime[i]==0){            an=an/prime[i]*(prime[i]-1);            while(nn%prime[i]==0)               nn/=prime[i];        }    }    if(nn>1)      an=an/nn*(nn-1);      return an;}LL qpow(LL a,LL k,LL c){    LL an=1;    a=a%c;    while(k){        if(k&1){            an=(an*a)%c;        }        k>>=1;        a=(a*a)%c;    }    return an;}LL ans;int main(){    getprime();    scanf("%lld%lld",&m,&p);    while(m--){        ans=0;        scanf("%lld%lld",&n,&q);        ou=oula(q);        matrix A;        A.a[0][0]=1;        A.a[0][1]=1;        A.a[1][0]=1;        A.a[1][1]=0;        matrix res=ks(A,n-1);        LL tmp=res.a[0][0];        //cout<<"ou="<<ou<<"  tmp="<<tmp<<endl;        ans=qpow(p,tmp,q)%q;        printf("%lld\n",ans);    }    return 0;}