#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
int x,y,d;
ll n;
void exgcd(int a,int b,int &x,int &y){
if(!b){
d=a,x=1,y=0;
}
else{
exgcd(b,a%b,y,x),y-=a/b*x;
}
}
int lcm(int a,int b){
return a/__gcd(a,b)*b;
}
int m1,r1,m2,r2;
void merge(){
exgcd(m1,m2,x,y); //求出一组 x,y 的可行解,此时 d 是 m1 和 m2 的 gcd
int c=r2-r1;
if(c%d){
cout<<"-1"; exit(0);
}
int p2=m2/d;
x=(x*c/d+p2)%p2;
int mod=lcm(m1,m2);
r1=(m1*x+r1+mod)%mod;
m1=mod;
}
signed main(){
cin>>n; //使用 __int128 的抽象操作
for(int i=1;i<=n;i++){
ll a,b;
cin>>a>>b;
m2=a,r2=b;
if(i>1){ //不是第一组数据可以 merge
merge();
}
else{
m1=m2,r1=r2; //此时的 m1 和 r1 是刚才读进来的 a 和 b
}
}
ll ans=r1%m1; //__int128 不是不能直接输出嘛,看我转 long long 再输出
cout<<ans;
return 0;
}
这几行是什么意思?
int p2=m2/d;
x=(x*c/d+p2)%p2;
int mod=lcm(m1,m2);
r1=(m1*x+r1+mod)%mod;
m1=mod;