【学术篇】SDOI2010 古代猪文

这里可能包含传送门

又双叒叕数论大杂烩...

定理什么我都不会证

题目很长很啰嗦但是题意很显然... 化完式子之后就是这么个东东:\(G^{\sum_{k|n}C_k^{\frac{n}{k}}}\ mod\ p\)

看上去好像也并不怎么好求...

而\(p\)是个质数,由于费马小定理,我们知道\(G^{p-1}\equiv 1(mod\ p)\),

所以我们相当于要求\(G^{{\sum_{k|n}C_k^{\frac{n}{k}}} \% (p-1)}\ mod\ p\)

看到大组合数取模自然想到Lucas定理...

可是这里的\(p-1\)并不是质数...

质因数分解:\(999911658=2*3*4679*35617\)(Emmmm这里我偷了个懒在线分解了←_←

对四个质数分别做Lucas就可以写出下面这一堆东西, 然后直接CRT(中国剩余定理(孙子定理))就行了...

\[\left\{\begin{matrix}
ans\equiv c_1(mod\ 2)
\\
ans\equiv c_2(mod\ 3)
\\
ans\equiv c_3(mod\ 4679)
\\
ans\equiv c_4(mod\ 35617)
\end{matrix}\right.
\]

好像就做完了OvO 说起来很简单的样子...

Emmmm,所以这题是不是还能强行给出模数然后考扩展Lucas

地球人看不懂的代码

(我对不起党对不起人民对不起社会地又双叒叕压行了)

谁让数论题一行一个函数压行太舒服了呢→_→

#include <cmath>

#include <cstdio>

typedef long long LL;

const int P=999911658;const int pr[]={2,3,4679,35617};LL fac[4][36666],c[4],N,G,blk; //懒得写质因数分解..(而且可能能避免一些麻烦??)

void exgcd(LL a,LL b,LL &x,LL &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}

LL qpow(LL a,LL b,LL p,LL s=1){for(;b;b>>=1,a=a*a%p)if(b&1)s=s*a%p;return s;}

LL inv(LL a,LL b,LL x=0,LL y=0){if(!a)return 0;exgcd(a,b,x,y);return(x%b+b)%b;}

void calcfac(){for(int i=0;i<4;++i){fac[i][0]=1;for(int j=1;j<=pr[i];++j)fac[i][j]=fac[i][j-1]*j%pr[i];}} //预处理阶乘

LL C(LL n,LL m,LL p,LL x=0){if(n<m) return 0; x=pr[p];return fac[p][n]*inv(fac[p][m],x)%x*inv(fac[p][n-m],x)%x;} //计算小于第p个质数的组合数

LL lucas(LL n,LL m,LL p,LL x=0){if(!m) return 1; x=pr[p];return C(n%x,m%x,p)*lucas(n/x,m/x,p)%x;} //基础的Lucas定理

LL CRT(LL x=0,LL y=0,LL ans=0){for(int i=0;i<4;++i)ans=(ans+c[i]*(P/pr[i])%P*inv(P/pr[i],pr[i])%P)%P;return ans;} //中国剩余定理辣~

void ANS(){for(int i=1;i<=blk;++i)if(N%i==0){for(int j=0;j<4;++j){if(i*i!=N) c[j]=(c[j]+lucas(N,i,j))%pr[j];c[j]=(c[j]+lucas(N,N/i,j))%pr[j];}}} //预处理阶乘对各个质数取模的答案(就是式子里的c1..c4)

int main(){scanf("%lld%lld",&N,&G);G%=P;if(!G){puts("0");return 0;}blk=sqrt(N);calcfac();ANS();printf("%lld",qpow(G,CRT(),P+1));}

我怎么会说注意事项

没有\(p_i^{k_i}\)这样的项就不需要扩展Lucas了...
阶乘处理的时候一定记得从0开始处理..
枚举k的时候只需从\(1\sim \sqrt n\)枚举, \(k|n\)就直接把\(C_{n}^{k}\)和\(C_{n}^{\frac{n}{k}}\)一起算了..(\(1\sim n\)枚举我猜会T飞→_→
其实数论题全开long long好像是个不错的主意OvO...
好像是有边界数据要特判来着...(见下)

95才能看的边界数据

#13出锅? 看这里!!!

P.S. 这组数据是我从luogu上交4遍分别输出\(N\ N\%10000\ G\ G\%10000\)抠出来的...

输入	输出
999911657 999911659	0

要是不加特判直接做会输出1 就WA了...

其实我第一遍WA意识到要加特判但是加错了OvO

(你可以看到我代码里的\(P\)是多少然后你应该能猜到出了什么问题→_→

这个部分真啥都没有

其实就是啥都没有...完结撒花~

巴特西