（扩展）中国剩余定理模板

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

中国剩余定理：$ O(nlog^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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; //注意是0，不是1
    while(b) { //按b的二进制展开，然后累加二进制位对应a的幂次，同时取模
        if(b & 1) res =(res + a) % mod; //b中有1则累加a的值，进行加法运算
        a = (a + a) % mod; //a每次乘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(r[i], M_i, lcm), x, lcm)) % lcm; //快速乘法取模，避免直接相乘导致数据溢出
    }
    return res;
}

扩展中国剩余定理：$ O(nlog^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
LL T, n, ans, r[maxn], m[maxn];
//求解二元一次方程：ax + by = gcd(a,b)
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;} //不妨假设 y=0，则x=1
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y; //x'=y,y'=x-a/b*y
    return res; //返回上一个状态
}
//扩展中国剩余定理：模数两两不都互素
LL ext_crt(LL *r, LL *m, LL n) { //余数：r，模数：m，同余方程个数：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; //答案
}
0%