1.中国剩余定理 (互质版)
#include <iostream> using namespace std; typedef long long LL; LL ex_gcd(LL a, LL b, LL &x, LL &y); LL China(LL re[], LL w[], LL len); int main() { LL n, i; LL a[50000], b[50000]; while (cin >> n) { for (i = 0; i < n; i++) { cin >> a[i] >> b[i];//除数,余数 } cout << China(b, a, n) << endl; } return 0; } LL ex_gcd(LL a, LL b, LL &x, LL &y)//扩展gcd { LL d = 0; if (b == 0) { x = 1; y = 0; return a; } d = ex_gcd(b, a%b, y, x); y -= a / b * x; return d; } LL China(LL re[], LL w[], LL len)//中国剩余原理 re余数数组 w除数数组 len数组长度 { LL i, d, x, y, m, n, ret; ret = 0; n = 1; for (i = 0; i < len; i++) n *= w[i]; for (i = 0; i < len; i++) { m = n / w[i]; d = ex_gcd(w[i], m, x, y); ret = (ret + y * m*re[i]) % n; } return (n + ret % n) % n; }
2.中国剩余原理(万能版)
慢一点的:
#include<iostream> #include<stdio.h> using namespace std; long long exgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1, y = 0; return a; } long long q = exgcd(b, a%b, y, x); y -= a / b * x; return q; } int main() { long long a1, c1, a2, c2, x, y, t; long long n; while (cin >> n) { long long flag = 1; cin >> a1 >> c1; for (long long i = 1; i < n; i++) { cin >> a2 >> c2; long long q = exgcd(a1, a2, x, y); if ((c2 - c1) % q != 0) { flag = 0; } t = a2 / q; x = ((x*(c2 - c1) / q) % t + t) % t; c1 = c1 + a1 * x; a1 = a1 * (a2 / q); } if (flag == 0) { cout << "-1" << endl; continue; } cout << c1 << endl; } return 0; }
快一点的:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL gcd(LL a, LL b) { if (b == 0) return a; return gcd(b, a%b); } LL ex_gcd(LL a, LL b, LL&x, LL& y) { if (b == 0) { x = 1, y = 0; return a; } LL d = ex_gcd(b, a%b, x, y); LL t = x; x = y; y = t - a / b * y; return d; } LL inv(LL a, LL n)//求a在模n乘法下的逆元,没有则返回-1 { LL x, y; LL t = ex_gcd(a, n, x, y); if (t != 1) return -1; return (x%n + n) % n; } //将两个方程合并为一个 bool merge(LL a1, LL n1, LL a2, LL n2, LL& a3, LL& n3) { LL d = gcd(n1, n2); LL c = a2 - a1; if (c%d) return false; c = (c%n2 + n2) % n2; c /= d; n1 /= d; n2 /= d; c *= inv(n1, n2); c %= n2; c *= n1 * d; c += a1; n3 = n1 * n2*d; a3 = (c%n3 + n3) % n3; return true; } //求模线性方程组x=ai(mod ni),ni可以不互质 LL ex_China(int len, LL* a, LL* n) { LL a1 = a[0], n1 = n[0]; LL a2, n2; for (int i = 1; i < len; i++) { LL aa, nn; a2 = a[i], n2 = n[i]; if (!merge(a1, n1, a2, n2, aa, nn)) return -1; a1 = aa; n1 = nn; } return (a1%n1 + n1) % n1; } LL a[1000], b[1000]; int main() { int i; int k; while (cin >> k) { for (i = 0; i < k; i++) cin >> a[i] >> b[i]; cout << ex_China(k, b, a); } return 0; }