先贴代码,解析待填坑。
#include<cstdio>
#include<algorithm>
#define int long long
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
int n,a[100005],b[100005];
int exgcd(int a,int b,int &x,int &y)
{
if (b==0)
{
x=1,y=0;
return a;
}
int ans=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return ans;
}
inline ll ksc(ll x,ll y,ll p)
{
ll z=(ld)x/p*y;
ll res=(ull)x*y-(ull)z*p;
return (res+p)%p;
}
signed main()
{
scanf("%lld",&n);
for (int i=1;i<=n;i++)
scanf("%lld%lld",&a[i],&b[i]);
int GCD,A1,A2,K1,K2,R,x=b[1],LCM;
for (int i=2;i<=n;i++)
{
if (b[i]<b[i-1]) swap(a[i],a[i-1]),swap(b[i],b[i-1]);
A1=a[i-1],K1,A2=a[i],K2,R=b[i]-b[i-1];
GCD=exgcd(A1,A2,K1,K2);LCM=A1/GCD*A2;
K1=(K1%A2+A2)%A2;
K1=ksc(K1,R/GCD,A2);
x=(ksc(K1,A1,LCM)+b[i-1])%LCM;
b[i]=x,a[i]=LCM;
}
printf("%lld",x);
return 0;
}