题解：P11532 [THUPC2025 初赛] 好成绩

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int n;
ll a[100010],p[100010];
ll gcd(ll a,ll b){
	if (b==0) return a;
	else return gcd(b,a%b);
}
void hebing(ll p1,ll a1,ll p2,ll a2,ll &p,ll &a){
	if (p1<p2) swap(p1,p2),swap(a1,a2);
	p=p1/gcd(p1,p2)*p2;  //新方程的模数是两个旧方程的模数的最小公倍数。
	a=a1;
	while (a%p2!=a2)
		a+=p1;
  //从 a1 开始，挨个试是有没有合适的余数。
} 

int main(){
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> p[i] >> a[i];
		a[i] %= p[i]; 
	}
	ll p_=1,a_=0;
	for (int i=1;i<=n;i++)
		hebing(p_,a_,p[i],a[i],p_,a_); //合并方程函数。
	cout << a_ << endl; 
}
//这个代码之所以可以过 P4777 是因为第十二行将模数较小的方程换到前面，从而减少了求 gcd 的时间。

//a_i 的最小公倍数是 1e18，所以 n=2 是才有可能卡掉，因为模数最大可以是 1e9。

//一旦有三个方程，模数最大只有 1e6，卡不掉了。

//此方法名叫大数翻倍法。

3
3 2
5 3
7 6

83