背景
今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何?
答曰：二十三。
古人的方法是：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。
这句话用算式写下来就是：(23 = 2 * 70 + 3 * 21 + 2 * 15 = 233，233 equiv 23 (mod 105))
这其中的70，21，15是如何得到的呢？
对上面的进行推论
- (x equiv 1(mod 3) y equiv 0(mod 3) z equiv 0(mod 3))
- (x equiv 0(mod 5) y equiv 1(mod 5) z equiv 0(mod 5))
- (x equiv 0(mod 7) y equiv 0(mod 7) z equiv 1(mod 7))
我们先求解 (x)。
不难发现 (x = 35y)， 同时有 (x equiv 1(mod 3), 35y equiv 1(mod 3)) 得到y = 2也就是求得x = 70。
同样的我们对后面的y, z用同样的方法求解得到分别是21，15。相信我们应该知道中国剩余定理是什么了。
其实整个求解的过程就相当于是求解逆元。
注意在执行上述时候，一定要满足任意两个模数是互质的
代码
/*
Code by lifehappy 2020:04:24
中国剩余定理
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int a[N], b[N], n;
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return ;
}
exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
return ;
}
void solve() {
ll m = 1, x, y, ans = 0;
for(int i = 1; i <= n; i++)
m *= b[i];
for(int i = 1; i <= n; i++) {
ll t = m / b[i];
exgcd(t, b[i], x, y);
ans = (ans + x * t * a[i]) % m;
}
ans = (ans + m) % m;
printf("%lld
", ans);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d %d", &a[i], &b[i]);//a[i]是余数，b[i]是模数。
solve();
return 0;
}
两道应用中国剩余定理的水题
Biorhythms 题目链接
这道题还记得还是在MOOC郭伟老师的算法课，枚举章节讲过的，以前也只会暴力。其实这是一道中国剩余定理的裸题。
/*
Code by lifehappy 2020:04:24
中国剩余定理的应用
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const ll b[4] = {0, 23, 28, 33};
ll a[4], ans;
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return ;
}
exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
return ;
}
void solve() {
ll m = 21252, x, y;
ans *= -1;
for(int i = 1; i <= 3; i++) {
ll t = m / b[i];
exgcd(t, b[i], x, y);
ans = (ans + x * t * a[i]) % m;
}
ans = (ans + m) % m;
printf("the next triple peak occurs in %lld days.
", ans == 0 ? m : ans);
}
int main() {
// freopen("in.txt", "r", stdin);
int t = 1;
while(scanf("%lld %lld %lld %lld", &a[1], &a[2], &a[3], &ans) && a[1] != -1) {
printf("Case %d: ", t++);
solve();
}
return 0;
}
P3868 [TJOI2009]猜数字 题目链接
/*
Code by lifehappy 2020:04:24
中国剩余定理，龟速乘
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
ll a[N], b[N];
int n;
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return ;
}
exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
return ;
}
ll slow_mult(ll a, ll b, ll mod) {
ll ans = 0;
while(b) {
if(b & 1) ans = (ans + a) % mod;
b >>= 1;
a = (a + a) % mod;
}
return ans;
}
void solve() {
ll m = 1, x, y, ans = 0;
for(int i = 1; i <= n; i++) m *= b[i];
for(int i = 1; i <= n; i++) {
ll t = m / b[i];
exgcd(t, b[i], x, y);
// ans = (ans + x * t * a[i]) % m;
ans = (ans + slow_mult(slow_mult(x % m + m, t, m), a[i] % m + m, m)) % m;
}
printf("%lld
", (ans + m) % m);
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
solve();
return 0;
}
中国剩余定理拓展
我们假定，求得前 (i) 项的解为 (x) 然后前 (i) 项的 (lcm) 为 (M) 我们可以的到 (x + kM) 是前 (i) 项的一个通解，带入第 (i) 项。
(x + kM equiv bi pmod {ai}) 移项也就是 (kM equiv {(bi - x)} pmod {ai})
我们的目的是求解K最后也就是求解这个方程组的解，然后再得到 (ans += k * M)。
一道板子题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N], b[N];
int n;
ll low_mult(ll a, ll n, ll mod) {
ll ans = 0;
while(n) {
if(n & 1) ans = (ans + a) % mod;
n >>= 1;
a = (a + a) % mod;
}
return ans;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
return gcd;
}
ll excrt() {
ll ans = b[1], M = a[1], x, y;
for(int i = 2; i <= n; i++) {
ll A = M, B = a[i], c = ((b[i] - ans) % B + B) % B;//
ll gcd = exgcd(A, B, x, y);
ll mod = B / gcd;
if(c % gcd) return -1;//无解的情况。
ll t = low_mult(x, c / gcd, mod);
ans += t * M;
M *= mod;
ans = (ans % M + M) % M;
}
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%lld %lld", &a[i], &b[i]);
printf("%lld
", excrt());
return 0;
}