中国剩余定理——acwing

题目：表达整数的奇怪方式

204. 表达整数的奇怪方式 - AcWing题库

分析

代码

a 与 b得最大公约数是正整数

例如：-6和3， 6和3，6和-3，都是3，都是一样的，所以不用管啥-a2，a2啥的，统统取正

#include<bits/stdc++.h>
using namespace std;

using ll = long long ;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    
    ll d = exgcd(b,a%b, x, y);
    
    int t = y; y = x-(a/b)*y; x = t;
    return d;
}

int main() {
    int _;
    cin >> _;
    
    int flag = 1;
    
    ll a1, m1;
    cin >> a1 >> m1;
    _ --;
    while(_ --) {
        ll a2, m2; 
        cin >> a2 >> m2;
        
        ll k1, k2;
        ll d = exgcd(a1,a2,k1,k2);
        // exgcd无解，k1,k2无解
        if((m2-m1)%d) {
            flag = 0; break;
        }
        // 扩大 k1,k2
        k1 *= (m2-m1)/d; 
        // 最小k1
        ll t = a2/d;
        k1 = (k1%t+t)%t; // 模加模，防止模出负数，得k1最小正解
        // 更新a1, m1
        m1 = a1*k1+m1;
        a1 = abs(a1/d*a2);
    }
    
    if(flag) cout << (m1%a1+a1)%a1 << endl;
    else puts("-1");
    
    return 0;
}