锐客网

  1. 首页 > it技术 > >

Lucas定理|[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】

[Description] 求
Lucas定理|[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】
文章图片

[Solution]
容易得到，
Lucas定理|[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】
文章图片

所以，重点在怎么求
Lucas定理|[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】
文章图片

如果是p-1是个质数，我们可以用sqrt(n)的时间枚举所有d,用Lucas定理分别计算求和即可。
但是我们发现p-1=2*3*4679*35617，并不是一个质数，所以Lucas定理不能用了吗？并不，我们可以算出这个合式分别对2、3、4679、35617的模值，写出四个同余方程，再用孙子定理求解即可。注意特判g==p的情况，此时费马小定理不成立，ans=0.
【Lucas定理|[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】】[Code]

#include #includetypedef long long ll; const int mod=999911659; ll prime[4]={2,3,4679,35617}; ll num[4],inver[4]; void exgcd(ll x,ll y,ll&a,ll&b){ if(!y) a=1,b=0; else{ exgcd(y,x%y,b,a); b-=a*(x/y); } }ll pow(ll a,ll n,int p){ ll ans=1; while(n){ if(n&1) ans=ans*a%p; a=a*a%p; n>>=1; } return ans; }ll C(ll m,ll n,ll p){ if(mm-n) n=m-n; ll ans=1,cm=1,cn=1; for(ll i=0; i

    推荐阅读


    上一篇：数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】

    下一篇：[Objective-C开发]|iOS 雪花动画与跑马灯