题解 P2480 【[SDOI2010]古代猪文】
XG_Zepto
2018-02-07 21:02:23
### 思路
观察题目,不难发现,我们需要在给定$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)
```