https://www.luogu.com.cn/problem/P4777
题意概述：给定一组同余方程：
\[x \equiv s_i \pmod {t_i}
\]
求方程的最小非负整数解，注意不保证所有 \(s_i\) 互质。
考虑从 \(res = px + q\) 到 \(res = s_iy+t_i\) 的拓展：
两式相减，整理得到 \(px - s_iy = t_i - q\)。
注意到这是一个丢番图方程，令 \(a = p，b = s_i，c = t_i - q，d = gcd(a,b)\)，（注意如果 \(c\) 不是 \(d\) 的倍数方程无解），使用拓展欧几里得算法求得一个特解 \(x'\)，模 \(b/d\) 调整成最小非负解。
那么通解 \(x = x' + k \cdot (b/d)\)，\(k\) 是任意整数，带入 \(res = px + q\)，得:
\[res = (b/d) \cdot p \cdot k + p \cdot x' + q
\]
这里 \(k\) 是变量，故 \(p\)，\(q\) 迭代成 $ (b/d) \cdot p $ ，$ p \cdot x' + q $。
最后 \(q\) 就是最小非负整数解。
实现上注意开 i128，同时迭代后 \(q\) 对 \(p\) 取模。
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;void solve(){int n;cin >> n;vector<ll> s(n+1),t(n+1);for (int i=1;i<=n;i++){cin >> s[i] >> t[i];}ll p=1,q=0;for (int i=1;i<=n;i++){ll a = p;ll b = s[i];ll c = t[i]-q;ll d = __gcd(a,b);ll x,y;function<void(ll,ll)> exgcd = [&](ll a,ll b){if (b==0){x = 1;y = 0;}else{exgcd(b,a%b);ll tx = x;ll ty = y;x = ty;y = tx-a/b*ty;}};exgcd(a,b);x = (i128)x*(c/d)%(b/d);x = ((i128)x+b/d)%(b/d);ll np = b/d*p;ll nq = ((i128)p*x%np+q)%np;p = np;q = nq;}cout << q << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}