中国剩余定理

背景

今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何?
答曰：二十三。
古人的方法是：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

这句话用算式写下来就是：(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("%lldn", 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.n", 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("%lldn", (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)。

一道板子题

P4777 【模板】扩展中国剩余定理（EXCRT）

#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("%lldn", excrt());
    return 0;
}