记录编号	571938	评测结果	AAAAAAAAAA
题目名称	3680.曹冲养猪	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-06-26 15:04:57	内存使用	0.00 MiB

#include <bits/stdc++.h>

using i64 = long long;
 
const int N = 30;
int n;
 
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) return (x = 1, y = 0), a;
    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
 
int main() {
    freopen("ccyz.in", "r", stdin); 
    freopen("ccyz.out", "w", stdout);
    std::cin >> n;
    i64 a1, m1, a2, m2;
    std::cin >> a1 >> m1;
    for (int i = 1; i <= n - 1; ++ i) {
        std::cin >> a2 >> m2;
        i64 k1, k2;
        i64 d = exgcd(a1, a2, k1, k2);
        k1 *= (m2 - m1) / d;
        i64 t = a2 / d;
        k1 = (k1 % t + t) % t;
        m1 += a1 * k1;
        a1 = std::abs(a1 / d * a2);
    }
    std::cout << ((m1 % a1 + a1) % a1) << '\n';
    return 0;
}