ACM常用模板合集

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 tp=x;x=y; y=tp-a/b*y; }int china() {int ans=0,lcm=1,x,y;for(int i=1;i<=k;++i) lcm*=b[i];for(int i=1;i<=k;++i){int tp=lcm/b[i];exgcd(tp,b[i],x,y);x=(x%b[i]+b[i])%b[i];//x要為最小非負(fù)整數(shù)解ans=(ans+tp*x*a[i])%lcm;}return (ans+lcm)%lcm; } lnt exgcd(lnt a,lnt b,lnt &x,lnt &y) {if(b==0){x=1;y=0;return a;}lnt gcd=exgcd(b,a%b,x,y);lnt tp=x;x=y; y=tp-a/b*y;return gcd; }lnt excrt() {lnt x,y,k;lnt M=bi[1],ans=ai[1];for(int i=2;i<=n;i++){lnt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;lnt gcd=exgcd(a,b,x,y),bg=b/gcd;if(c%gcd!=0) return -1; x=mul(x,c/gcd,bg);ans+=x*M;M*=bg;ans=(ans%M+M)%M;}return (ans%M+M)%M; }

總結(jié)

以上是生活随笔為你收集整理的数论--中国剩余定理模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。