链接:

https://www.acwing.com/problem/content/206/

题意:

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足?i∈[1,n],x≡mi(mod ai)。

思路:

扩展中国剩余定理模板题.

代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;LL R[50], M[50];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, x, y); LL tmp = y; y = x-(a/b)*y; x = tmp; return d;}LL ExCRT(){ LL m = M[1], r = R[1], x, y, gcd; for (int i = 2;i <= n;i++) { gcd = ExGcd(m, M[i], x, y); if ((r-R[i])%gcd != 0) return -1; x = (r-R[i])/gcd*x%M[i]; r -= m*x; m = m/gcd*M[i]; r %= m; } return (r%m+m)%m;}int main(){ scanf("%d", &n); for (int i = 1;i <= n;i++) scanf("%lld%lld", &M[i], &R[i]); printf("%lld\n", ExCRT()); return 0;}