[SDOI2010]古代猪文

题解：

一看就是一道数学题了。

根据欧拉定理，必须要处理的是$sum_i|n C(n,i)\space mod \space \phi(p)$

令A等于这个大式子。

phi(p)=999911658=2*3*4679*35617

是四个质数的乘积。

看来就类似扩展LUCAS了。

但是，指数只有1

所以，我们可以求出：

A = a1 mod 2

A = a2 mod 3

A = a3 mod 4679

A = a4 mod 35617

（a1~a4怎么求？LUCAS定理即可。）

这是一个同余方程，要解出A

其实，我们就要A = a5 mod 999911658

中国剩余定理合并，返回a5即可。

不会CRT？右转：CRT&EXCRT 中国剩余定理及其扩展

注意，求的A是在mod 999911658下的。不能用其他质数mod完。除了ti，即Mi在mod mi下的逆元。

 

最后计算G^a5 mod 999911659

但是，出题人比较狡诈，还是有坑的。

因为，欧拉定理的适用的前提是：gcd(G,mod)=1;

扩展欧拉定理更是如此。

如果G=mod，那么就不互质了。

如果这时候，恰好a5=0，那么我们会输出1

其实答案无论如何是0

G=mod判掉即可。

 

代码：

#include<bits/stdc  .h>using namespace std;typedef long long ll;const int N=35666;const int mod=999911659;const int P[4]={2,3,4679,35617};ll jie[4][N],inv[4][N];ll f[4][2];ll n,g;ll qm(ll x,ll y,ll p){    ll ret=1%p;    while(y){        if(y&1) (ret*=x)%=p;        (x*=x)%=p;        y>>=1;    }    return ret;}ll C(ll a,ll b,ll id){    //if(b==0) return 1;    ll ret=jie[id][a]*inv[id][a-b]%P[id]*inv[id][b]%P[id];    //cout<<" C "<<a<<" "<<b<<" "<<id<<" "<<P[id]<<" : "<<jie[id][a]<<" "<<inv[id][a-b]<<" "<<inv[id][b]<<" "<<ret<<endl;    return ret;}ll Lucas(ll a,ll b,ll id){    if(a<b) return 0;    if(a<P[id]) return C(a,b,id);    return (Lucas(a%P[id],b%P[id],id)*Lucas(a/P[id],b/P[id],id))%P[id];}ll merge(){//ret x%phi(mod)    ll phi=mod-1;    ll ret=0;    for(int i=0;i<4;i  ){        ll cheng=1;        for(int j=0;j<4;j  ){            if(i==j) continue;            cheng*=P[j];        }        ll iv=qm(cheng%P[i],P[i]-2,P[i]);        cheng=(cheng*f[i][1]%phi*iv%phi);        (ret =cheng)%=phi;    }    return ret;}int fac[100001],tot;void divi(){    for(int i=1;(ll)i*i<=n;i  ){        if(n%i==0){            fac[  tot]=i;            if(i!=n/i) fac[  tot]=n/i;        }    }}int main(){    scanf("%lld%lld",&n,&g);    if(g==mod){        printf("0");return 0;    }    divi();    //cout<<tot<<endl;    //for(int i=1;i<=tot;i  ) cout<<fac[i]<<" ";cout<<endl;    for(int i=0;i<4;i  ){        jie[i][0]=1;        inv[i][0]=1;        for(int j=1;j<P[i];j  ){            jie[i][j]=(jie[i][j-1]*j)%P[i];            inv[i][j]=qm(jie[i][j],P[i]-2,P[i]);        }        ll sum=0;        for(int j=1;j<=tot;j  ){            (sum =Lucas(n,fac[j],i))%=P[i];            //cout<<" j "<<fac[j]<<" "<<sum<<endl;        }        //cout<<i<<" "<<P[i]<<" : "<<sum<<endl;        f[i][0]=P[i];        f[i][1]=sum;    }    //cout<<jie[2][3]<<" "<<qm(6,P[2]-1,P[2])<<" "<<inv[2][3]<<endl;    //cout<<Lucas(4,4,0)<<endl;    ll mi=merge();    ll ans=qm(g,mi,mod);    printf("%lld",ans);    return 0;}/*   Author: *Miracle*   Date: 2018/10/2 20:41:08*/

 

来源：http://www.icode9.com/content-4-34651.html