【模板】excrt

题目

https://www.luogu.com.cn/problem/P4777

思路

发现之前忘记写博客了
https://www.luogu.com.cn/blog/niiick/solution-p4777

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+77;
ll a[N],b[N];int n;
ll mul(ll x,ll y,ll mod)
{
	return ((x*y)-(ll)((long double)x*y/mod)*mod+mod)%mod;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1; y=0; return a;
	}
	ll gcd=exgcd(b,a%b,x,y);
	ll t=x; x=y; y=t-(a/b)*y;
	return gcd;
}
ll excrt()
{
	ll x,y,M=b[1],ans=a[1];
	for(int i=2; i<=n; i++)
	{
		ll A=M,B=b[i],C=((a[i]-ans)%B+B)%B;
		ll gcd=exgcd(A,B,x,y),mod=B/gcd;
		if(C%gcd!=0) return -1;
		x=mul(x,C/gcd,mod);
		ans+=x*M;
		M*=mod;
		ans=(ans%M+M)%M;
	}
	return (ans%M+M)%M;
}
int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%lld%lld",&b[i],&a[i]);
	printf("%lld",excrt());
}