系统介绍了基础数论算法，涵盖最大公约数与最小公倍数的欧几里得算法、质数判定与筛法（埃氏筛、线性筛）、算术基本定理及分解质因数。此外还详细讲解了欧拉函数、费马小定理、乘法逆元求法、裴蜀定理、扩展欧几里得算法以及中国剩余定理（CRT）和扩展中国剩余定理（EXCRT）。文章包含核心代码实现与时间复杂度分析，适合算法初学者入门。
最大公约数（Greatest Common Divisor，常缩写为 gcd）
最小公倍数（Least Common Multiple，常缩写为 lcm）
欧几里得算法也称辗转相除法，可以求出两个整数的最大公约数。
算法流程：
设 a>b：
因为 a mod b 会不断减小，因此可以用递归进行求解。
代码实现：
long long gcd(long long a, long long b) {
if(!b) return a; // 如果 b 等于 0，说明 a 就是最大公约数
return gcd(b, a % b);
}
时间复杂度：
求 gcd(a,b) 会遇到两种情况：
第二种情况会让 a 至少折半，因此最多执行 logn 次。第一种情况不会多于第二种，因此时间复杂度为 O(logn)。
证明
证明 gcd(a,b)=gcd(b,a%b)，思路：先证左边等于右边，再证右边等于左边。
设 a>b，a mod b = a − k * b，其中 k=a/b，为整数：若 d 是 (a,b) 的公约数，则 d∣a 且 d∣b，于是 d∣(a−kb)，则 d∣(a%b)；因此 d 也是 (b,a%b) 的公约数；若 d 是 (b,a%b) 的公约数，则 d∣b 且 d∣(a−kb)，于是 d∣(a−kb+kb)=d∣(a)；因此 d 也是 (a,b) 的公约数；
所以 (a,b) 的公约数与 (b,a%b) 的公约数相同，那么最大公约数也相同。
秦九韶算法是一种将一元 n 次多项式的求值问题转化为 n 个一次式的算法。其大大简化了计算过程，即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法。
代码实现
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;
}
时间复杂度
枚举到 sqrt(n)，因此时间复杂度为 O(sqrt(N))。
【引入】
上面学习了如何判断一个数是否是质数，如果此时想知道 [1, n] 中有多少个素数呢？或者是 [1, n] 中的素数里面，第 k 个素数是多少？
[1, n] 中的素数全部记录下来。算法思想
k(k > 1) 倍就是合数。小优化
x 之后，可以从该数的 x 倍向后筛，因此小于 x 的倍数一定被之前筛过了。代码实现
const int N = 1e6 + 10;
bool st[N]; // 当前这个数有没有被筛掉
int p[N]; // 记录质数
int cnt; // 统计质数个数
// 埃氏筛
void get_prime(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) // 没有被标记，说明是质数
{
p[++cnt] = i; // 记录这个质数
// 从 i*i 开始，因为小于 i 的倍数已经被划掉了
for(int j = i * i; j <= n; j += i) // 筛掉这个质数的倍数
{
st[j] = true;
}
}
}
}
时间复杂度
埃氏筛的时间复杂度为：O(n log log n)。
线性筛法，又称欧拉筛法。
算法思想
代码实现：
const int N = 1e6 + 10;
int n, q;
bool st[N];
int p[N], cnt;
// 欧拉筛
void get_prime(int n) {
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)。
因此，枚举 [2, sqrt(N)] 中所有的数，如果能整除 n 就一直除下去。如果最后剩下的数大于 1，那就是大于 sqrt(n) 的因子。
小优化
代码实现
const int N = 1e6 + 10;
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]++; // 不要忘记判断最后一个质数
}
时间复杂度
枚举到 sqrt(N)，因此时间复杂度为 O(sqrt(N))。但是最优情况下会达到 O(logn)。
模板题：
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;
}
对于一个整数 x，若 d 是 x 的约数，那么 x/d 也是 x 的约数。也就是说，除了完全平方数，约数都是成对出现的。因此，可以用试除法求一个整数的所有约数。
枚举 1∼sqrt(x) 之间的整数，判断是否能整除 x。
试除法也能求出一个整数的约数个数以及约数总和。
代码实现
const int N = 1e6 + 10;
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;
}
}
}
时间复杂度
枚举到 sqrt(N)，因此时间复杂度为 O(sqrt(N))。
因此，一个整数 n 的约数个数的上限为 2*sqrt(N)。
如果用试除法分别求每一个数的约数，时间复杂度过高。
可以反过来想，对于每个数 d，[1,n] 中以 d 为约数的数就是 d 的倍数，也就是 d,2d,3d... n/d *d。因此可以用倍数法求出 [1,n] 每个数的约数集合。
代码实现
const int N = 1e6 + 10;
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);
}
时间复杂度
#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;
}
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;
}
时间复杂度：枚举到 sqrt(N )，因此时间复杂度为 O(sqrt(N ))。
问题背景：需要知道 [1,n] 中，每一个数的欧拉函数。
代码实现
const int N = 1e6 + 10;
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)。
性质
这就解释了为什么之前遇到需要取模的题目，如果只涉及加减乘运算，我们可以边计算边取模。而存在除法的时候，不能随意取模。
若 a,m 互质，且满足同余方程 ax ≡ 1(mod m)，则称 x 是 a 模 m 的乘法逆元，记作 a^-1
对于算式 (b÷a)modp，可以写成 (b×a^-1) mod p，其中 a×a^-1 ≡1(modp)。因此，对于这个除数 a，如果能够找到一个数 x，使的两者的乘积在模 m 时为 1，即 ax≡1(modp)，那么就可以用 x 替代 a^-1 去取模。
例如：(25÷5)mod3，对于 5 而言，(5×2)≡1(mod3)，因此用 2 代替 5^-1，原式变为 (25×2)mod3=50mod3=2。
我们会学习三种求乘法逆元的方式，一直要注意每种方式的使用条件。
那么 a 在模 p 意义下的其中一个乘法逆元就是 a^(p-2)，用快速幂就可以快速求出。
由费马小定理得，当 a,p 互质，且 p 为质数时，a^(p-1) ≡ 1(mod p)，也就是 a×a^(p-2) ≡1(modp)。
一定要注意，利用费马小定理求逆元的时候，模数 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;
}
时间复杂度
序列求和
#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;
}
裴蜀定理又称贝祖定理：
例如：6x+8y=gcd(6,8)=2，一定有整数解。其中 x=−1,y=1 就是一组解。
#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;
}
裴蜀定理遗留问题：如何求 ax+by=gcd(a,b) 的一组整数解？利用扩展欧几里得算法即可求解。
当 b != 0 时：
代码实现
typedef long long LL;
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 的解:
模板题：
代码：
#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;
}
求同余方程 ax ≡ b(mod m) 的解。
例如：求 4x ≡ 2(mod 6)，其中一个解为 x = 2。
同余方程可以转换为二元一次不定方程：
那么，就可以用扩展欧几里得算法求出 x 的值。
因此，利用扩欧算法也可以求出乘法逆元。并且不需要模数 m 是质数，仅需 gcd(a,m)=1，也就是 a,m 互质即可。
模板题：
乘法逆元一般用于求 a/b (modp) 的值。先算出 b 在模 p 意义下的乘法逆元 b^−1，然后计算 a×b^−1(modp) 的值，就可以将除法转化为乘法。
下面总结一下求逆元的各种方法。
代码实现
// 必须要保证 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;
}
代码实现
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;
}
代码实现
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;
}
}
递推原理：
模板题：
打表所有的阶乘
模数 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;
}
时间复杂度
南北朝时期的《孙子算经》中有个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
用数学公式翻译过来就是一个线性同余方程组：
线性同余方程组：求
的最小非负整数解。
原理
中国剩余定理是基于'构造法'得出的结果。以下给出 n=3 的构造过程，n 等于任意数的构造过程是一样的。
对于方程组，记 M = m1 × m2 × m3，构造解：
只要能构造出这样的 x，那么 x 就是我们要的解。
中国剩余定理的构造方式
当 x 加减 M 的若干倍时，依旧是满足方程，因此最小非负整数解就是
n 取任意数的时候，构造方式也是同理：
计算结果：
计算每一个方程的 Ci：
const int N = 1e5 + 10;
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;
}
模板题：
中国剩余定理（CRT）只能处理所有模数两两互质的情况，如果模数不互质，CRT 就不适用了。
求解线性同余方程组：
算法思想：将任意整数 X 不断迭代成最终解。
补上一个方程 x ≡ 0 (mod1)，最终解 ret = x × 1+0。
模板题：
代码：
#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;
}
可以求两点横纵坐标的差值的 gcd
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online