Bzoj1951 [Sdoi2010]古代猪文
首先由欧拉定理易知当A与p互质时A^B %p=A^(B%φ(p) ) %p
这里p是一个质数 于是φ(p)=p-1=999911658
然后由于这个数不是质数 难以处理 我们将它分解质因数 然后对于每个质因数的解用中国剩余定理合并即可
然后就是999911658有一个很好的性质 999911658=2*3*4679*35617 每个质因数的次数都是1次
于是我们可以套用卢卡斯定理 预先处理出对于每个质因数的阶乘和阶乘的逆元即可
注意此题有个细节 就是欧拉定理中a与p必须互质 而当a=0(即G=p)时gcd(a,p)=p
所以有一组数据是专门卡这个地方的 这组数据是999911657 999911659 取模后是0^0 于是得到1 但是答案是0
于是我们做一些处理 A^B %p=A^(B%φ(p)+φ(p) ) %p
这样就没问题了
评论