一、題目：

洛谷模板

二、代碼：

#include<iostream> #include<cstdio> #include<cstring>#define LL long long #define mem(s,v) memset(s,v,sizeof(s)) #define FILE(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)using namespace std; template<class Type> inline Type read(Type num){Type x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return f*x; }const int maxn=100005;int n; LL ai[maxn],bi[maxn];inline LL mult(LL a,LL b,LL p){LL ret=0;for(;b;b>>=1){if(b&1)ret=(ret+a)%p;a=(a+a)%p;}return ret; }inline LL exgcd(LL a,LL b,LL &x,LL &y){if(b==0){x=1;y=0;return a;}LL d=exgcd(b,a%b,x,y);LL z=x;x=y;y=z-a/b*y;return d; }inline LL excrt(void){LL x,y;LL M=bi[1],ans=ai[1];for(register int i=2;i<=n;++i){LL a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;LL gcd=exgcd(a,b,x,y),bg=b/gcd;if(c%gcd!=0)return -1;x=mult(x,c/gcd,bg);ans+=x*M;M*=bg;ans=(ans%M+M)%M;}return (ans%M+M)%M; }int main(){n=read(n);for(register int i=1;i<=n;++i){bi[i]=read(bi[i]);ai[i]=read(ai[i]);}printf("%lld\n",excrt());return 0; }

轉載于:https://www.cnblogs.com/little-aztl/p/9738718.html

總結

以上是生活随笔為你收集整理的【模板】扩展中国剩余定理（EXCRT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。