中国剩余定理 & 扩展中国剩余定理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[12],b[12],mod=1;
ll ksmul(ll a,ll b)
{
	ll ans=0;
	while(b)
	{
		if(b&1) ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1; 
	}
	return ans;
}
void ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0) {
		x=1,y=0; return;
	}
	ex_gcd(b,a%b,x,y);
	ll t=x;
	x=y,y=t-a/b*y;
}
void CRT(int n)
{
	ll ans=0,Mi,x,y;
	for(int i=1;i<=n;i++) {
		Mi=mod/b[i];
		ex_gcd(Mi,b[i],x,y);
		x=(x%b[i]+b[i])%b[i];
		ans=(ans+ksmul(ksmul(a[i],x),Mi)+mod)%mod;
	}
	printf("%lld",ans);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&b[i]);
		mod*=b[i];
	}
	CRT(n);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
ll a[maxn],b[maxn];
ll ksmul(ll a,ll b,ll mod)
{
	ll ans=0;
	while(b)
	{
		if(b&1) ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans;
}
void ex_gcd(ll a,ll b,ll &x,ll &y,ll &gcd)
{
	if(b==0) {
		x=1,y=0,gcd=a; return;
	}
	ex_gcd(b,a%b,x,y,gcd); 
	ll t=x;
	x=y,y=t-a/b*y;
}
ll EX_CRT(int n)
{
	ll ans=b[1],M=a[1],x,y,c,gcd;
	for(int i=2;i<=n;i++) {
		c=(b[i]-ans%a[i]+a[i])%a[i];
		ex_gcd(M,a[i],x,y,gcd);
		if(c%gcd) return -1;
		x=ksmul(x,c/gcd,a[i]/gcd);
		ans+=x*M;
		M*=a[i]/gcd;
		ans=(ans%M+M)%M;
	}
	return ans;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
	printf("%lld",EX_CRT(n));
	return 0;
}