（扩展）中国剩余定理例题汇总

luogu P3868.[TJOI2009]猜数字

题目描述：

现有两组数字，每组k个，第一组中的数字分别为：$ a_1,a_2,\cdots,a_k $ 表示，第二组中的数字分别用 $ b_1,b_2,\cdots,b_k$ 表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的 $ i,n - a_i $ 能被 $ b_i $ 整除。

输入格式：

输入数据的第一行是一个整数 $ k,(1\leq k \leq 10)$。接下来有两行，第一行是：$ a_1,a_2,\cdots,a_k $，第二行是$ b_1,b_2,\cdots,b_k$。

输出格式：

输出所求的整数n。

输入样例：

1
2
3

3
1 2 3
2 3 5

输出样例：

说明

所有数据中，第一组数字的绝对值不超过 $ 10^9 $（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过 $ 10^{18} $。每个测试点时限1秒。
注意：对于C/C++语言，对64位整型数应声明为long long，如使用scanf, printf函数（以及fscanf, fprintf等），应采用%lld标识符。

思路：

要使得 $ b_i | (n-a_i) $，则有 $n\equiv a_i \;(mod\; b_i)$，即问题求解转化为裸的中国剩余定理。
为避免数据溢出，要处理一下两个坑点：①余数都要先处理为绝对值最小的整数；②因为直接乘法取模容易发生数据溢出，所以要改为快速乘法取模运算！

AC代码1：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL n, r[maxn], m[maxn];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL quick_mul(LL a, LL b, LL mod){//快速乘法，防止两数相乘爆long long，时间复杂度为log(b)
    LL res = 0LL;
    while(b) {
        if(b & 1) res =(res + a) % mod;
        a = (a + a) % mod; //每次乘2
        b >>= 1;
    }
    return res;
}
LL crt(LL *r, LL *m, LL n) { //中国剩余定理
    LL lcm = 1LL, res = 0LL, M_i, x, y;
    for(LL i = 0; i < n; ++i) lcm *= m[i]; //先求出所有方程的最小公倍数
    for(LL i = 0; i < n; ++i) {
        M_i = lcm / m[i];
        ext_gcd(M_i, m[i], x, y);
        x = (x % m[i] + m[i]) % m[i]; //取最小非负整数解
        //res = (res + r[i] * M_i * x) % lcm;
        res = (res + quick_mul(quick_mul(M_i, r[i], lcm), x, lcm)) % lcm;
    }
    return res;
}
int main() {
    while(cin >> n) {
        for(LL i = 0; i < n; ++i) cin >> r[i];
        for(LL i = 0; i < n; ++i) cin >> m[i], r[i] = (r[i] % m[i] + m[i]) % m[i]; //余数的绝对值不超过模数的绝对值
        cout << crt(r, m, n) << endl;
    }
    return 0;
}

AC代码2：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL n, r[maxn], m[maxn];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL ext_crt(LL *r, LL *m, LL n) { //扩展中国剩余定理
    LL lcm = m[0], res = r[0], x, y, gcd, mod;
    for(LL i = 1; i < n; ++i) {
        gcd = ext_gcd(lcm, m[i], x, y);
        if((r[i] - res) % gcd) return -1;
        x *= (r[i] - res) / gcd;
        mod = m[i] / gcd;
        x = (x % mod + mod) % mod;
        res = res + lcm * x;
        lcm = lcm / gcd * m[i];
    }
    return res;
}
int main() {
    while(cin >> n) {
        for(LL i = 0; i < n; ++i) cin >> r[i];
        for(LL i = 0; i < n; ++i) cin >> m[i], r[i] = (r[i] % m[i] + m[i]) % m[i]; //余数的绝对值不超过模数的绝对值
        cout << ext_crt(r, m, n) << endl;
    }
    return 0;
}

poj 2891 Strange Way to Express Integers

Problem Description

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers $ a_1,a_2,\cdots,a_k $. For some non-negative m, divide it by every $a_i (1 \leq i \leq k)$ to find the remainder ri. If $ a_1,a_2,\cdots,a_k $ are properly chosen, m can be determined, then the pairs $(a_i, r_i) $ can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

Input

The input contains multiple test cases. Each test cases consists of some lines.
Line 1: Contains the integer k.
Lines $ 2 \sim k + 1 $: Each contains a pair of integers $a_i, r_i (1 \leq i \leq k) $.

Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one.
If there are no possible values, output -1.

Sample Input

1
2
3

2
8 7
11 9

Sample Output

Hint

All integers in the input and the output are non-negative and can be represented by 64-bit integral types.

思路：

裸的扩展中国剩余定理。

AC代码：

#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
LL n, r[maxn], m[maxn];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL ext_crt(LL *r, LL *m, LL n) {
    LL lcm = m[0], res = r[0], x, y, gcd, mod;
    for(LL i = 1; i < n; ++i) {
        gcd = ext_gcd(lcm, m[i], x, y);
        if((r[i] - res) % gcd) return -1;
        x *= (r[i] - res) / gcd;
        mod = m[i] / gcd;
        x = (x % mod + mod) % mod;
        res = res + lcm * x;
        lcm = lcm / gcd * m[i]; //先除后乘，避免数据溢出
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    while(cin >> n) {
        for(LL i = 0; i < n; ++i) cin >> m[i] >> r[i];
        cout << ext_crt(r, m, n) << endl;
    }
    return 0;
}

hdu 1573 X问题

Problem Description

求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的第一行为两个正整数 $N,M (0 < N \leq 1000000000, 0 < M \leq 10)$，表示X小于等于N，数组a和b中各有M个元素。接下来两行，每行各有M个正整数，分别为a和b中的元素。

Output

对应每一组输入，在独立一行中输出一个正整数，表示满足条件的X的个数。

Sample Input

3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9

Sample Output

1
2
3

1
0
3

思路：

裸的扩展中国剩余定理。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL T, n, k, tot, ans, r[maxn], m[maxn];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL ext_crt(LL *r, LL *m, LL n, LL sum) {
    LL lcm = m[0], res = r[0], x, y, gcd, mod;
    for(LL i = 1; i < n; ++i) {
        gcd = ext_gcd(lcm, m[i], x, y);
        if((r[i] - res) % gcd) return -1;
        x *= (r[i] - res) / gcd;
        mod = m[i] / gcd;
        x = (x % mod + mod) % mod;
        res = res + lcm * x;
        lcm = lcm / gcd * m[i];
    }
    if(res > sum) return -1;
    else return (sum - res) / lcm + (res != 0); //求解res + lcm * k ≤ sum
}
int main() {
    while(cin >> T) {
        while(T--) {
            cin >> tot >> n;
            for(LL i = 0; i < n; ++i) cin >> m[i];
            for(LL i = 0; i < n; ++i) cin >> r[i];
            ans = ext_crt(r, m, n, tot);
            cout << (ans == -1 ? 0 : ans)  << endl;
        }
    }
    return 0;
}

hdu 3579 Hello Kiki

Problem Description

One day I was shopping in the supermarket. There was a cashier counting coins seriously when a little kid running and singing “门前大桥下游过一群鸭，快来快来数一数，二四六七八”. And then the cashier put the counted coins back morosely and count again…
Hello Kiki is such a lovely girl that she loves doing counting in a different way. For example, when she is counting X coins, she count them N times. Each time she divide the coins into several same sized groups and write down the group size $ M_i $ and the number of the remaining coins $ A_i $ on her note.
One day Kiki’s father found her note and he wanted to know how much coins Kiki was counting.

Input

The first line is T indicating the number of test cases.
Each case contains N on the first line, $ M_i(1 \leq i \leq N)$ on the second line, and corresponding $ A_i(1 \leq i \leq N)$ on the third line.
All numbers in the input and output are integers.
$ 1 \leq T \leq 100, 1 \leq N \leq 6, 1 \leq M_i \leq 50, 0 \leq A_i < M_i $

Output

For each case output the least positive integer X which Kiki was counting in the sample output format. If there is no solution then output -1.

Sample Input

2
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76

Sample Output

1 2	Case 1: 341 Case 2: 5996

思路：

裸的扩展中国剩余定理。注意：求最小的正整数解。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 10;
LL T, n, k, ans, r[maxn], m[maxn];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL ext_crt(LL *r, LL *m, LL n) {
    LL lcm = m[0], res = r[0], x, y, gcd, mod;
    for(LL i = 1; i < n; ++i) {
        gcd = ext_gcd(lcm, m[i], x, y);
        if((r[i] - res) % gcd) return -1;
        x *= (r[i] - res) / gcd;
        mod = m[i] / gcd;
        x = (x % mod + mod) % mod;
        res = res + lcm * x;
        lcm = lcm / gcd * m[i];
    }
    return res ? res : (res + lcm); //求最小的正整数解
}
int main() {
    while(cin >> T) {
        for(LL cas = 1; cas <= T; ++cas) {
            cin >> n;
            for(LL i = 0; i < n; ++i) cin >> m[i];
            for(LL i = 0; i < n; ++i) cin >> r[i];
            cout << "Case " << cas << ": ";
            cout << ext_crt(r, m, n) << endl;
        }
    }
    return 0;
}