算法：基础数论

1. 最大公约数和最小公倍数

【约数和倍数】

• 如果 a 除以 b 没有余数，那么 a 就是 b 的倍数，b 就是 a 的约数，记作 b∣a。

• 约数，也称因数。

【最大公约数和最小公倍数】

最大公约数（Greatest Common Divisor，常缩写为 gcd）

• 一组整数的公约数，是指同时是这组数中每一个数的约数的数。

• 一组整数的最大公约数，是指所有公约数里面最大的一个。

最小公倍数（Least Common Multiple，常缩写为 lcm）

• 一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。

• 一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。

求两个数的 gcd 与 lcm 时的性质

• 对于两个数 a 和 b，gcd(a,b)×lcm(a,b)=a×b。也就是最大公约数乘以最小公倍数等于两个数的乘积。

• 因此，一般先求最大公约数，然后用这个性质求最小公倍数。

【欧几里得算法】

欧几里得算法也称辗转相除法，可以求出两个整数的最大公约数。

算法流程：

设 a>b：

• 如果 b 是 a 的约数，那么 b 就是两者的最大公约数；

• 如果 b 不是 a 的约数，那么 gcd(a,b)=gcd(b,amodb)。

因为 a mod b 会不断减小，因此可以用递归进行求解。

代码实现：

LL gcd(LL a, LL b)
{
if(!b) return a; // 如果 b 等于 0，说明 a 就是最大公约数
return gcd(b, a % b);
}
/*
LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a % b);
}
*/

时间复杂度：

求 gcd(a,b) 会遇到两种情况：

第二种情况会让 a 至少折半，因此最多执行 logn 次。第一种情况不会多于第二种，因此时间复杂度为 O(logn)。

证明

证明 gcd(a,b)=gcd(b,amodb)，思路：先证左边等于右边，再证右边等于左边。

设 a>b，a mod b = a − k * b，其中 k=a/b，为整数：

所以 (a,b) 的公约数与 (b,amodb) 的公约数相同，那么最大公约数也相同。

模板题

B3736 [信息与未来 2018] 最大公约数 – 洛谷

【秦九韶算法】

秦九韶算法是一种将一元 n 次多项式的求值问题转化为 n 个一次式的算法。其大大简化了计算过程，即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法。

【利用唯一分解定理】

2. 质数的判定

【质数和合数】

• 一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；
• 否则称为合数。
• 其中，质数又称素数。
• 规定 1 既不是质数也不是合数。

试除法判断质数

• 对于一个数 x，根据定义，可以从 [2,x−1] 一个一个尝试，判断 x 能否被整除。
• 优化思路：若 a 是 x 的约数，那么 x/a 也是 x 的约数。因此仅需判断较小的 a，枚举到 x​ 即可。

代码实现

bool isprime(int x)
{
if(x <= 1) return false; // 小于等于 1 的数不考虑

// 试除法判断是否是质数 – 只需枚举到 sqrt(x)
for(int i = 2; i <= x / i; i++) // 防溢出的写法
{
if(x % i == 0) return false;
}
return true;
}

时间复杂度

枚举到 n​，因此时间复杂度为 O(​)。

模板题

P5736 【深基7.例2】质数筛 – 洛谷

3. 筛质数

【引入】 

上面学习了如何判断一个数是否是质数，如果此时想知道 [1, n] 中有多少个素数呢？或者是 [1, n] 中的素数里面，第 k 个素数是多少？

• 一个自然的想法就是从 2 开始，依次向后对每一个自然数进行一次质数检验。

• 但是这种解法相对暴力，我们这里介绍两种方法，能够快速地将 [1, n] 中的素数全部记录下来。

【第一种筛法：埃氏筛法】

算法思想

• 对于任意一个大于 1 的正整数，那么它的 k(k > 1) 倍就是合数。

• 因此，如果我们从小到大考虑每个数，然后同时把当前这个数的所有倍数记为合数，没有被标记的数就是素数。

小优化

• 找到一个质数 x 之后，可以从该数的 x 倍向后筛，因此小于 x 的倍数一定被之前筛过了。

代码实现

bool st[N]; // 当前这个数有没有被筛掉
int p[N]; // 记录质数
int cnt; // 统计质数个数

// 埃氏筛
void get_prime()
{
for(LL i = 2; i <= n; i++)
{
if(!st[i]) // 没有被标记，说明是质数
{
p[++cnt] = i; // 记录这个质数
// 从 i*i 开始，因为小于 i 的倍数已经被划掉了
for(LL j = i * i; j <= n; j += i) // 筛掉这个质数的倍数
{
st[j] = true;
}
}
}
}

时间复杂度

埃氏筛的时间复杂度为：O(n log log n)。

【第二种筛法：线性筛法】

线性筛法，又称欧拉筛法。

算法思想

• 在埃氏筛法中，它会将一个合数重复多次标记。如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 O(n) 了。

• 我们的做法是，让每一个合数被它的最小质因数筛掉。

• 从前往后遍历每一个树 i；

• 1.用 i 的质数倍去筛（因为要被最小质因数筛掉）

• 2.如果 i 是质数的倍数时，停止 

代码实现：

int n, q;
bool st[N];
int p[N], cnt;

// 欧拉筛
void get_prime()
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) p[++cnt] = i; // 如果没标记过，就是质数

// 枚举所有的质数
for(int j = 1; 1ll * i * p[j] <= n; j++)
{
st[i * p[j]] = true;
if(i % p[j] == 0) break;
/*
这个判定条件能让每一个合数被自己的最小质因数筛掉。
1. 如果 i 是合数，枚举到最小质因数的时候跳出循环
2. 如果 i 是质数，枚举到自身时跳出循环
注意，在筛的过程中，我们还能知道 p[j] 是 i 的最小质因数
*/
}
}
}

时间复杂度

每个数只会被自身最小的质因数筛掉一次，时间复杂度为 O(n)。

4. 算术基本定理

【算术基本定理】

【分解质因数】

• 分解质因数就是将一个合数用质因数相乘的形式表示出来，例如：360=2^3×3^2×5^1

【试除法分解质因数】

• n 的所有因数中，不会有两个大于 n​。
• 因此，枚举 [2, ] 中所有的数，如果能整除 n 就一直除下去。如果最后剩下的数大于 1，那就是大于 ​ 的因子。

小优化

• 如果我们提前打出来一个素数表，枚举所有素数的话，时间复杂度能进一步降低。

代码实现

int c[N]; // c[i] 表示 i 这个质数出现的次数

void deprime(int x)
{
for(int i = 2; i <= x / i; i++)
{
int cnt = 0;
while(x % i == 0) // 只要有这个因子，就除尽，并且计数
{
x /= i;
cnt++;
}
c[i] += cnt;
}
if(x > 1) c[x]++; // 不要忘记判断最后一个质数
}

时间复杂度

枚举到 ​，因此时间复杂度为 O(​)。但是最优情况下会达到 O(logn)。

模板题：

P2043 质因子分解 – 洛谷

P10495 阶乘分解 – 洛谷

P10495题解：

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1e6 + 10;
const int M = 2e4 + 10;
const int INF = 0x3f3f3f3f;
using PII = pair<int, int>;
using ull = unsigned long long;
#define endl '\\n'
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dxx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dyy[] = {1, -1, 0, 0, 1, 1, -1, -1};
ull base = 131;

int n;
int c[N];
int p[N];
int cnt;
bool st[N];

void get_prime(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) p[++cnt] = i;
for(int j = 1; i * p[j] <= n; j++)
{
st[i * p[j]] = true;
if(i % p[j] == 0) break;
}
}
}
void solve()
{
cin >> n;
get_prime(n);
// 用质数来筛
for(int i = 1; i <= cnt; i++)
{
int t = 0;
for(int j = p[i]; j <= n; j *= p[i])
{
c[p[i]] += n / j;
}
cout << p[i] << " " << c[p[i]] << endl;
}

}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
//cin >> _;
while(_–)
{
solve();
}
return 0;
}

5. 约数

【求一个整数的所有约数】

对于一个整数 x，若 d 是 x 的约数，那么 x/d 也是 x 的约数。也就是说，除了完全平方数，约数都是成对出现的。因此，可以用试除法求一个整数的所有约数。

枚举 1∼x​ 之间的整数，判断是否能整除 x。

试除法也能求出一个整数的约数个数以及约数总和。

代码实现

int d[N], cnt;

void get_d(int x)
{
// 注意从 1 开始循环
for(int i = 1; i <= x / i; i++)
{
if(x % i == 0)
{
d[++cnt] = i;
if(i != x / i) d[++cnt] = x / i;
}
}
}

时间复杂度

• 枚举到​，因此时间复杂度为 O(​)。

因此，一个整数 n 的约数个数的上限为 2。

【求 [1,n] 每个数的约数集合】

如果用试除法分别求每一个数的约数，时间复杂度过高。

可以反过来想，对于每个数 d，[1,n] 中以 d 为约数的数就是 d 的倍数，也就是 d,2d,3d… n/d *d。因此可以用倍数法求出 [1,n] 每个数的约数集合。

代码实现

int n;
vector<int> d[N];

void get_d()
{
for(int i = 1; i <= n; i++) // 枚举所有约数
for(int j = 1; j <= n / i; j++) // 约数的倍数
d[i * j].push_back(i);
}

时间复杂度

• n 倍的调和数，约为 O(nlogn)。

约数个数的和

#include <iostream>
using namespace std;
#define int long long
signed main()
{
int n; cin >> n;
int sum = 0;
for(int i = 1; i <= n/2; i++)
{
sum += (n/i);
}
sum += n – n/2;
cout << sum << endl;

return 0;
}

6. 欧拉函数

【互质】

• a 与 b 互质：说明 a 与 b 的最大公约数是 1。

【欧拉函数】

• 对于一个数 n，在 1∼n 中，与 n 互质的数的个数，就是欧拉函数，用 φ(n) 表示。

• 比如：φ(1)=1，φ(2)=1，φ(3)=2，φ(4)=2，φ(5)=4……

【积性函数】

• 若函数 f(n) 满足：f(1)=1，且 f(xy)=f(x)f(y)，x,y∈N∗ 都成立。则 f(n) 为积性函数。

【欧拉函数的性质】

【试除法求单个数的欧拉函数】

int phi(int n)
{
int ret = n;
for(int i = 2; i <= n / i; i++)
{
if(n % i == 0)
{
ret = ret / i * (i – 1); // 先除后乘，保证不会溢出
while(n % i == 0) n /= i;
}
}
// 别忘记判断最后一个数
if(n > 1) ret = ret / n * (n – 1);
return ret;
}

时间复杂度：枚举到 ​，因此时间复杂度为 O(​)。

【欧拉筛打表欧拉函数】

问题背景：需要知道 [1,n] 中，每一个数的欧拉函数。

代码实现 

int n;
bool st[N];
int p[N], cnt;
int phi[N];

void get_phi()
{
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!st[i])
{
p[cnt++] = i;
phi[i] = i – 1;
}
for(int j = 1; 1ll * i * p[j] <= n; j++)
{
int x = i * p[j]; // 当前要筛的数
st[x] = true;
if(i % p[j] == 0)
{
phi[x] = p[j] * phi[i];
break;
}
else
{
phi[x] = (p[j] – 1) * phi[i];
}
}
}
}

时间复杂度：与线性筛时间复杂度一致，为 O(n)。

7.费小马定理

【同余式】

• 如果两个整数 a,b 模 m 的余数相同，则称 a, b 模 m 同余，记作：a ≡ b(mod m)。

• 例如：7 ≡ 4(mod 3)

性质

• 同加性：若 a ≡ b(mod m)，则 a + c ≡ b + c (mod m)

• 同乘性：若 a ≡ b(mod m)，则 ac ≡ bc(mod m)

• 也就是说，对于同余的两个数，执行完相同的加减乘操作后，它们两者还是同余的。

• 但是同余不满足同除性，例如 20≡2(mod3)，左右都除以 10，结果就不是同余的。

这就解释了为什么之前遇到需要取模的题目，如果只涉及加减乘运算，我们可以边计算边取模。而存在除法的时候，不能随意取模。

【费马小定理】

• 如果 p 为质数，且 a,p 互质，则 a^(p−1) ≡ 1(mod p)。

• 例如：2^(5−1)≡1(mod5)

【乘法逆元】

• 若 a,m 互质，且满足同余方程 ax ≡ 1(mod m)，则称 x 是 a 模 m 的乘法逆元，记作 

• 例如：8x≡1(mod5)，解得 x=2,7,…

应用

• 如果涉及除法，是不满足分配律的。利用乘法逆元就可以解决这一问题。

对于算式 (b÷a)modp，可以写成 (b×) mod p，其中 a×≡1(modp)。因此，对于这个除数 a，如果能够找到一个数 x，使的两者的乘积在模 m 时为 1，即 ax≡1(modp)，那么就可以用 x 替代  去取模。

• 例如：(25÷5)mod3，对于 5 而言，(5×2)≡1(mod3)，因此用 2 代替 ，原式变为 (25×2)mod3=50mod3=2。

【求乘法逆元（一）— 费马小定理 + 快速幂】

我们会学习三种求乘法逆元的方式，一直要注意每种方式的使用条件。

• 由费马小定理得，当 a,p 互质，且 p 为质数时， ≡ 1(mod p)，也就是 a×≡1(modp)。

• 那么 a 在模 p 意义下的其中一个乘法逆元就是 ，用快速幂就可以快速求出。

• 例如：(25÷5)mod3，其中 5 在模 3 下的一个乘法逆元为 5^(3-2)=5。因此用 5 代替 5−1，原式变为 (25×5)mod3=125mod3=2。

一定要注意，利用费马小定理求逆元的时候，模数 p 一定要是质数，且 a,p 互质。不过在我们一般做题的时候，取模的值一般都是质数，比如 1e9+7,1e9+9,998244353，并且 a 一般都比这些模数小，所以可以用费马小定理求逆元。如果 p 不是质数，我们会用后面学到的扩展欧几里得算法求逆元。

代码实现

#include <iostream>
using namespace std;

typedef long long LL;

// 必须要保证 a,p 互质，且 p 为质数。
LL qpow(LL a, LL b, LL p)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}

int main()
{
LL x, p; cin >> x >> p;
cout << qpow(x, p – 2, p) << endl;

return 0;
}

时间复杂度

• 与快速幂时间复杂度一致，为 O(logn)。

序列求和

序列求和

8. 欧拉定理与扩展欧拉定理

模板题：

P5091 【模板】扩展欧拉定理 – 洛谷

#include <iostream>

using namespace std;
#define int long long

int a, m;
string s;
int get_phi(int m)
{
int ret = m;
for(int i = 2; i <= m/i; i++)
{
if(m % i == 0)
{
ret = ret / i * (i – 1);
while(m % i == 0) m /= i;
}
}
if(m > 1) ret = ret / m * (m – 1);
return ret;
}

int get_b(string& s, int p)
{
int t = 0;
bool flag = false;
for(int i = 0; i < s.size(); i++)
{
t = t * 10 + s[i] – '0';
if(t >= p)
{
flag = true;
t %= p;
}
}
if(flag) t += p;
return t;
}

int qpow(int a, int b, int p)
{
int ret = 1;
while(b)
{
if(b & 1) ret = (ret * a) % p;
a = a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}
signed main()
{
cin >> a >> m >> s;
int phi = get_phi(m);
int b = get_b(s, phi);
cout << qpow(a,b,m);

return 0;
}

9. 裴蜀定理

【裴蜀定理】

裴蜀定理又称贝祖定理：

• 一定存在整数 x,y，满足 ax+by=gcd(a,b)。
• 可以用来判定不定方程是否存在整数解。

例如：6x+8y=gcd(6,8)=2，一定有整数解。其中 x=−1,y=1 就是一组解。

【裴蜀定理的推论】

【注意】

• a,b 的正负是不影响结果的。因为 a,b 如果存在解，那么 a,−b 也一定存在解，只不过在 a,b 解的基础上添上一个负号。
• 因此，在用欧几里得算法求 gcd(a,b) 时，为了避免出现负数，可以带入 a,b 的绝对值。

P4549 【模板】裴蜀定理 – 洛谷

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int n; cin >> n;
int ret; cin >> ret;
ret = abs(ret);
for(int i = 2; i <= n; i++)
{
int x; cin >> x;
ret = gcd(ret, abs(x));
}
cout <<ret << endl;
return 0;
}

10. 扩展欧几里得算法

【扩展欧几里得算法】

裴蜀定理遗留问题：如何求 ax+by=gcd(a,b) 的一组整数解？利用扩展欧几里得算法即可求解。

• 当 b=0 时，ax+by=ax，因此有一组解为：x=1,y=0；

• 当 b != 0 时：

  

代码实现

LL exgcd(LL a, LL b, LL& x, LL& y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL x1, y1, d;
// 先求出下一层的 x1 和 y1
d = exgcd(b, a % b, x1, y1);
// 求当前层
x = y1, y = x1 – a / b * y1;
return d;
}

int main()
{
int a, b, x, y;
int d = exgcd(a, b, x, y);
cout << x << " " << y << endl;
return 0;
}

时间复杂度

与欧几里得算法时间复杂度一致，为 O(logn)。

【扩欧求二元一次不定方程的解】

求解二元一次不定方程 ax+by=c 的解:

模板题：

P5656 【模板】二元一次不定方程 (exgcd) – 洛谷

代码：

#include <iostream>

using namespace std;
#define int long long

int exgcd(int a, int b, int& x, int& y)
{
if(b == 0)
{
x = 1,y = 0;
return a;
}
int x1, y1, d;
d = exgcd(b, a%b, x1, y1);
x = y1;
y = x1 – a/b * y1;
return d;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t; cin >> t;
while(t–)
{
int a, b, c;
cin >> a >> b >> c;
int x0, y0; // 特解
int d = exgcd(a, b, x0, y0);
if(c % d != 0)
{
cout << -1 << endl;
continue;
}
// c 的特解：
int x1 = x0* c / d;
int y1 = y0* c / d;

int k1 = b/d;
int k2 = a/d;

int minx = (x1 % k1 + k1) % k1;
minx = minx == 0 ? k1 : minx;
int maxy = (c – a * minx) / b;

int miny = (y1 % k2 + k2) % k2;
miny = miny == 0 ? k2 : miny;
int maxx = (c – b*miny) / a;

if( maxy <= 0)
{
cout << minx << " " << miny << endl;
}
else
{
int t = (maxx – minx) / k1 + 1;
cout << t << " " << minx << " " << miny << " " <<
maxx << " " << maxy << "\\n";
}

}
return 0;
}

11. 同余方程

【同余方程】

求同余方程 ax ≡ b(mod m) 的解。

例如：求 4x ≡ 2(mod 6)，其中一个解为 x = 2。

【扩欧算法求同余方程的解】

同余方程可以转换为二元一次不定方程：

• 由 ax ≡ b (mod m) 可得：ax = ym + b，移项得 ax − my=b；
• 令 y = −y，就变成二元一次不定方程：ax + my=b；
• 由裴蜀定理得，当 gcd(a,m)∣b 时，有解。

那么，就可以用扩展欧几里得算法求出 x 的值。

【扩欧算法求乘法逆元】

• 特殊的，如果 b 等于 1，原方程变为 ax≡1(modm)，解出的 x 实际上就是 a 在模 m 意义下的乘法逆元。

因此，利用扩欧算法也可以求出乘法逆元。并且不需要模数 m 是质数，仅需 gcd(a,m)=1，也就是 a,m 互质即可。

模板题：

【模板】同余方程

12. 逆元

【乘法逆元】

乘法逆元一般用于求 a/b ​(modp) 的值。先算出 b 在模 p 意义下的乘法逆元 b^−1，然后计算 a×b^−1(modp) 的值，就可以将除法转化为乘法。

下面总结一下求逆元的各种方法。

方法一：费马小定理 + 快速幂

• 问题：求 a 在模 m 意义下的逆元。
• 前提条件：a,m 互质，且 m 是质数。
• 方法：求出 a^(m−2)，就是 a 在模 m 意义下的逆元。
• 时间复杂度：O(logm)。

代码实现

// 必须要保证 a,m 互质，且 m 为质数。
LL qpow(LL a, LL b, LL m)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % m;
b >>= 1;
a = a * a % m;
}
return ret;
}

int main()
{
LL x, m; cin >> x >> m;
cout << qpow(x, m – 2, m) << endl;
return 0;
}

方法二：扩欧算法求逆元

• 问题：求 a 在模 m 意义下的逆元。
• 前提条件：a,m 互质。
• 方法：解同余方程 ax≡1(modm)。
• 时间复杂度：O(logm)。

代码实现

LL exgcd(LL a, LL b, LL& x, LL& y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
LL x1, y1, d;
d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 – a / b * y1;
return d;
}

int main()
{
LL a, m; cin >> a >> m;
LL x, y, d;
d = exgcd(a, m, x, y);

if(d == 1) cout << (x % m + m) % m << endl;

return 0;
}

方法三：递推法

• 问题：求 1∼n 中所有的数在模 p 意义下的逆元。
• 前提条件：1∼n 中所有的数都与 p 互质。
• 方法：线性递推：
  • 当 i=1：inv[1]=1
  • 当 i>1：inv[i]=p−(p/i)×inv[pmodi]modp
• 时间复杂度：O(n)。

代码实现

LL n, p;
LL inv[N];

void get_inv()
{
inv[1] = 1;
for(int i = 2; i <= n; i++)
{
inv[i] = p – p / i * inv[p % i] % p;
}
}

递推原理：

模板题：

P3811 【模板】模意义下的乘法逆元 – 洛谷

方法四：打表i的阶乘的逆元（求组合数）

打表所有的阶乘

• f[i] 表示 i 的阶乘 mod p 的值，f[i]=f[i−1]×i。
• 这样，从左往右递推一遍，就可以把所有的阶乘全部维护出来。

•  模数 p 一般是一个较大的质数，比如 1e9+7。此时 p > n > m 时，并且 p 是质数，那么对于 [1,n] 里的所有数，p 都与它们互质，因此逆元一定存在。对于阶乘求逆元，也可以递推。

代码实现

int n, p;
LL f[N], g[N];

LL qpow(LL a, LL b, LL p)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}

void init()
{
f[0] = 1;
for(int i = 1; i <= n; i++)
{
f[i] = f[i – 1] * i % p;
}
g[n] = qpow(f[n], p – 2, p);
for(int i = n – 1; i >= 0; i–)
{
g[i] = (i + 1) * g[i + 1] % p;
}
}

LL C(int n, int m)
{
if(n < m) return 0;
return f[n] * g[n – m] % p * g[m] % p;
}

时间复杂度

• 打表：O(n)
• 查询：O(1)

13. 中国剩余定理

引入 – 线性同余方程组

南北朝时期的《孙子算经》中有个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

用数学公式翻译过来就是一个线性同余方程组：

线性同余方程组：求

的最小非负整数解。

中国剩余定理 (CRT)

• 前提：所有的模数 m1​, m2 ​,…, mn​ 两两互质。因此中国剩余定理的使用比较局限。

原理

中国剩余定理是基于 “构造法” 得出的结果。以下给出 n=3 的构造过程，n 等于任意数的构造过程是一样的。

对于

方程组，记 M = m1 ​× m2 ​× m3​，构造解：

只要能构造出这样的 x，那么 x 就是我们要的解。

中国剩余定理的构造方式

当 x 加减 M 的若干倍时，依旧是满足方程，因此最小非负整数解就是

n 取任意数的时候，构造方式也是同理：

例如

算法流程

代码实现

int n;
LL r[N], m[N];

LL qmul(LL a, LL b, LL p)
{
LL ret = 0;
while(b)
{
if(b & 1) ret = (ret + a) % p;
b >>= 1;
a = (a + a) % p;
}
return ret;
}

void exgcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1, y = 0;
return;
}
LL x1, y1;
exgcd(b, a % b, x1, y1);
x = y1, y = x1 – a / b * y1;
}

LL crt()
{
LL M = 1;
for(int i = 1; i <= n; i++) M *= m[i];

LL ret = 0;
for(int i = 1; i <= n; i++)
{
LL c = M / m[i];
LL x, y;
exgcd(c, m[i], x, y);
x = (x % m[i] + m[i]) % m[i]; // 补成最小非负整数

ret = (ret + qmul(qmul(c, x, M), r[i], M)) % M;
}
return ret;
}

模板题：

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 – 洛谷

15. 扩展中国剩余定理

中国剩余定理的缺陷

中国剩余定理（CRT）只能处理所有模数两两互质的情况，如果模数不互质，CRT 就不适用了。

扩展中国剩余定理 – EXCRT

求解线性同余方程组：

算法思想：将任意整数 X 不断迭代成最终解。

算法步骤

例如

补上一个方程 x ≡ 0 (mod1)，最终解 ret = x × 1+0。

模板题：

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

代码：

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n;
LL m[N], r[N];

LL qmul(LL a, LL b, LL p)
{
LL sum = 0;
while(b)
{
if(b & 1) sum = (sum + a) % p;
b >>= 1;
a = (a + a) % p;
}
return sum;
}

LL exgcd(LL a, LL b, LL& x, LL& y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
LL x1, y1;
LL d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 – a / b * y1;
return d;
}

LL excrt()
{
LL M = 1, ret = 0;
for(int i = 1; i <= n; i++)
{
LL a = M, b = m[i], c = r[i] – ret;
// 防溢出：把 c 补成最小非负整数
c = (c % b + b) % b;

// ax + by = c
LL x, y, d;
d = exgcd(a, b, x, y);
if(c % d) return -1;
// x -> ax + by = 1
// x -> ax + by = c -> x * (c / d)
LL k1 = b / d;
x = qmul(x, c / d, k1);
x = (x % k1 + k1) % k1;

ret = ret + x * M;
M = k1 * M;
ret = (ret % M + M) % M;
}
return ret;
}

int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> m[i] >> r[i];

cout << excrt() << endl;

return 0;
}

16：求两点的连线上对多少个顶点

可以求两点横纵坐标的差值的gcd