题解 P2480 【[SDOI2010]古代猪文】

XG_Zepto

2018-02-07 21:02:23

Solution

### 思路 观察题目,不难发现,我们需要在给定$G$,$N$的情况下,求 $G^{\sum_{i|N}C_N^i} \ mod \ 999911659$ 的值。所以,我们只需要求出$G$的幂的值就可以进行计算。 然而数据范围告诉我们,先求$\sum_{i|N}C_N^i$再进行计算是会爆空间的。所以,我们利用费马小定理的一个推论。 $a^b\equiv a^{b \ mod \ (p-1)}\pmod{p} \ \ \ \ \ \ (a\ne p)$ 于是,我们考虑对组合数取模。发现$p-1$,即$999911658$不是质数,将它分解,得$2*3*4679*35617$ 。所以,我们先利用Lucas定理对组合数分别取模,然后用中国剩余定理求出$G$的幂,最后用快速幂求得答案。 ### 代码 卢卡斯定理: ``` int C(int n,int m,int x){ if(n<m)return 0; return fac[x][n]*inverse(fac[x][n-m]*fac[x][m],t[x])%t[x]; }//fac为对于4个质数分别预处理的阶乘,inverse为逆元。 int lucas(int n,int m,int x){ if(m==0)return 1; return C(n%t[x],m%t[x],x)*lucas(n/t[x],m/t[x],x)%t[x]; } ``` 中国剩余定理: ``` int Chinese_Remainder_Theorem(){ int a1,b1,a2,b2,a,b,c,x,y; a1=t[0],b1=ANS[0]; for(int i=1;i<4;i++){ a2=t[i],b2=ANS[i]; a=a1;b=a2;c=b2-b1; exgcd(a,b,x,y); x=((c*x)%b+b)%b; b1=b1+a1*x;a1=a1*b; } return b1;//ANS记录对于4个质数取模得到的不同答案,t存储四个质数 } void exgcd(int a,int b,int &x,int &y){ if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } ``` 主程序只是一个简单的找约数,分别计算并累加记录至ANS数组的过程,不再赘述。 输出: ``` ksm(G,Chinese_Remainder_Theorem(),P) ```