https://mp.zhizhuma.com/webappv2/videoLecture/video-t54tec.htm?resId=40045384&idSign=13bb0e&resType=1&crId=68748620&crIdSign=672be0&bookId=530726&bookIdSign=6d2dbe&entityId=530726&entityType=1&_wxId=530726&_wxType=1&_wxSrc=1&_rand=1762141908445 #include<bits/stdc++.h> using namespace std; #define int long long #define ll __int128 #define Attack return #define On 0 #define Titan ; const int N=1e5+5,M=1e5+5,mod=998244353; const ll INF=1ll<<60; int n,a,b; ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } ll d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } ll A,B,x,y; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n,A=1,B=0; for(int i=1;i<=n;i++){ cin>>a>>b; ll gd=exgcd(A,a,x,y); x=(B-b)/gd*x; B=B-A*x; A=a/gd*A; B=(B%A+A)%A; } int ans=(B%A+A)%A; cout<<ans<<"\n"; Attack On Titan }