提交记录

代码:

#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[1000005],b[1000005],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]*b[idx+1]/gcd(b[idx],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;
}

错误数据（供参考）：

输入：
77
6 2
39 32
13 6
14 6
36 8
39 32
3 2
8 0
3 2
41 17
5 1
12 8
40 16
33 11
21 20
39 32
36 8
38 14
33 11
14 6
15 11
4 0
18 8
36 8
38 14
26 6
10 6
25 11
34 10
15 11
17 10
4 0
12 8
9 8
25 11
27 8
6 2
38 14
41 17
16 0
11 0
30 26
23 6
29 18
33 11
8 0
25 11
35 6
38 14
21 20
30 26
16 0
41 17
34 10
33 11
40 16
3 2
2 0
14 6
29 18
37 2
3 2
39 32
33 11
11 0
7 6
41 17
3 2
26 6
22 0
3 2
41 17
6 2
10 6
23 6
13 6
15 11
正确输出：5288194736
我的输出：2985513264845168

谢谢！