谢谢大佬

谢谢大佬

谢谢大佬

#include<bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>inline void rd(T &x)
{
	x=0;char q=getchar();int f=1;
	while(q<'0'||q>'9')if(q=='-')f=-1;
	while(q>='0'&&q<='9')
	{
		x=(x<<1)+(x<<3)+q-'0';
		q=getchar(); 
	}
	x=x*f;
}
int n;
const int N=1e5+10; 
int a[N],m[N];
int mod=1;
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int z=x;x=y,y=z-y*(a/b);
	return d;
}
int gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b)
{
	return a/gcd(a,b)*b;
}
int mul(int x,int y)
{
	int ans=0,k=x;
	while(y)
	{
		if(y&1)ans+=k,ans%=mod;
		y>>=1;
		k<<=1;
		k%=mod;
	}
	return ans;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
		scanf("%lld%lld",&m[i],&a[i]);
    	mod=lcm(mod,m[i]);//所有数的lcm,以后来取模
	}
	int M=a[1],xgb=m[1];
	for(int i=2;i<=n;i++)
	{
		exgcd(xgb,m[i],x,y);
		x=(((x%m[i])+m[i])%m[i]);
		x*=((((a[i]-M))%m[i])+m[i])%m[i]/gcd(xgb,m[i]);
		M=M+mul(x,xgb);//常规excrt
		M%=mod;
		xgb=lcm(xgb,m[i]);
	}
	cout<<M%mod;
	
	
    return 0;
}