题解：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

得到答案 83，符合标准，输出。

原创：某钟姓 dalao。