88分了,代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
lll gcd(ll a,ll b){
if(a<b)return gcd(b,a);
if(a%b==0)return b;
return gcd(b,a%b);
}
lll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;return a;
}
lll k=exgcd(b,a%b,x,y);
lll t=x;
x=y;
y=t-a/b*y;
return k;
}
ll n,a[100005],b[100005],idx=0;
int main(){
scanf("%lld",&n);
for(register int i=0;i<n;i++){
scanf("%lld%lld",&b[i],&a[i]);
}
while(idx!=n-1){
lll lcm=b[idx]/gcd(b[idx],b[idx+1])*b[idx+1],p1=b[idx]/gcd(b[idx],b[idx+1]),p2=b[idx+1]/gcd(b[idx],b[idx+1]);
ll x,y;lll g=exgcd(p1,p2,x,y);
x=(x+lcm)%lcm;
a[idx+1]=(a[idx]+((a[idx+1]-a[idx])/gcd(b[idx],b[idx+1]))*x*b[idx]+lcm)%lcm;
b[idx+1]=lcm;
idx++;
}
printf("%lld\n",(a[n-1]+b[n-1])%b[n-1]);
return 0;
}
```
错误数据不变
by tmpliyijiang @ 2023-12-02 18:30:47
已 A,此帖结
by tmpliyijiang @ 2024-01-04 15:39:35