表达整数的奇怪方式

题目描述

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai) 。
输入格式
第 1 行包含整数 n 。
第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi ，数之间用空格隔开。
输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
数据范围
1≤ai≤2^31−1,0≤mi<ai 1≤n≤25
所有 mi 的最小公倍数在 64 位有符号整数范围内。
输入样例：
2
8 7
11 9
输出样例：
31

我们需要找到一个最小的k1,k2，使得等式成立（因为要求x最小，而a和m都是正数）。
2. 用扩展欧几里得算法找出一组解
我们已知a1,m1,a2,m2
，可以用扩展欧几里得算法算出一个k′1,k′2
使得：
k′1∗a1+k′2∗(−a2)=gcd(a1,−a2)
无解判断：
若gcd(a1,−a2)∤m2−m1，则无解。
我们设d=gcd(a1,−a2),y=(m2−m1)d
承接上文，我们只需让k1,k2
分别扩大y倍，则可以找到一个k1,k2
满足①式：
k1=k′1∗y,k2=k′2∗y
3. 找到最小正整数解
我们知道一个性质：
②k1=k1+k∗a2d
k2=k2+k∗a1d
k为任意整数，这时新的k1,k2
仍满足①式。

代码

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lld\n", m1);
    return 0;
}