BZOJ 1951 [Sdoi2010] 古代猪文

发布于 2017-10-30  141 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1951

题意:见好长的原题面。


易知

$$ans=G^{\sum_{k|n}^{ }\binom{n}{k}}$$

底数和指数太大了,怎么办

$$a^b\equiv a^{b \ mod\ \varphi \(p)} \ (mod\ p)(1)$$

$$a^b\equiv (a\ mod \ p)^b(2)$$

这样就可以了,需要注意的是 (1) 式成立当且仅当\(gcd(a,p)=1\)

此时存在反例\(G=P \ and \ \varphi (p)|b \) 使得答案为 1(应为 0),将 (1) 式转化为

$$a^b\equiv a^{b \ mod\ \varphi \(p)+\varphi \(p)} \ (mod\ p)(1)$$

求解即可。

发现此时模数\(\varphi \(p)\) 不为质数,但是\(\varphi \(p)=999911658=2\times 3\times 4679\times 35617\)

可以分别计算,再中国剩余定理合并。

 


一个非常弱的准退役OIER