数论

质数

从 2 开始的整数定义的，小于等于 1 的数既不是质数也不是合数。

在大于 1 的整数中，如果只包含 1 和这个数本身两个约数，就被称为质数或者叫素数。

质数的判定

试除法

如果 d∣nd|n，那么 nd∣n\frac{ n }{ d }|n，只枚举每对约数中些较小那个的数，令 d≤ndd \le \frac{ n }{ d }，解得 d≤nd \le \sqrt{n}。

从 2 一直枚举到 n\sqrt{n}，时间复杂度：O(n)O(\sqrt{n})

1
2
3
4
5
6
7
8
9
10
bool is_prime(int n) {
  if(n<2) return false;
  // 为防止溢出建议写 i<=n/i
  for(int i=2;i<=n/i;i++) {
    if(n%i==0) {
      return false;
    }
  }
  return true;
}

试除法判定质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
bool is_prime(int n) {
    if(n<2) return false;
    for(int i=2;i<=n/i;i++) {
        if(n%i==0) return false;
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    while(n--) {
        int a;
        cin >> a;
        if(is_prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

分解质因数

分解质因数

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
#include <iostream>
using namespace std;
int n, a;
void divide(int n) {
    for(int i=2;i<=n/i;i++) {
        // 从 2 开始寻找 n 的质因子
        if(n%i==0) {
            int s = 0;
            // 如果 n 能整除 i，就将所有 i 除干净，同时记录 i 的指数
            while(n%i==0) {
                s++;
                n/=i;
            }
            cout << i << " " << s << endl;
        }
    }
    // 最多有一个大于根号n的质因子，单独处理一下
    if(n>1) cout << n << " " << 1 << endl;
}
int main() {
    cin >> n;
    while(n--) {
        cin >> a;
        divide(a);
        cout << endl;
    }
    return 0;
}

质数筛

质数定理：1 ~ n 中大约有 nln⁡n\frac{n}{\ln n} 个质数。

埃氏筛法时间复杂度：O(n⋅log⁡log⁡n)O(n \cdot \log\log n)

线性筛法时间复杂度：O(n)O(n)

筛质数的原理：如果 p 没有被筛掉，说明在之前 2 ~ p-1 的过程中都没有把 p 筛掉，说明 p 不是 2 ~ p-1 的倍数，2 ~ p-1 都不是 p 的约数，因此 p 是质数。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
const int N = 1e6+10;

int prime[N], cnt;
bool st[N];

//朴素筛法-O(nlogn)
void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]) prime[cnt++] = i;
        for(int j = i+i; j <= n; j += i)
            st[j] = true;
    }
}

//埃式筛法-O(nloglogn)
// 只判断 2 ~ p-1 中的质数是不是 p 的约数
void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]){
            prime[cnt++] = i;
            for(int j = i; j <= n; j += i)
                st[j] = true;
        }
    }
}

//线性筛法-O(n), n = 1e7 的时候基本就比埃式筛法快一倍了
//算法核心：x 仅会被其最小质因子筛去
#include <iostream>
using namespace std;
const int N = 1e6+10;
int primes[N];
int cnt;
int st[N];
void get_primes(int n) {
    // 从 2 开始判断每个数是不是素数
    for(int i=2;i<=n;i++) {
        // 如果没被筛掉，就是素数
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;primes[j]<=n/i;j++) {
            // 从小到大枚举每个质数，筛掉 primes[j]*i
            // 对于任意一个合数 x，假设 primes[j] 为 x 最小质因子，当 i<x/primes[j] 时，一定会被筛掉
            st[primes[j]*i] = true;
            // 如果 primes[j] 是 i 的最小质因子，就 break
            if(i%primes[j]==0) break;
            /*
            1.i%primes[j] == 0, primes[j] 定为 i 最小质因子，primes[j] 也定为 primes[j]*i 最小质因子
            2.i%primes[j] != 0, primes[j] 定小于 i 的所有质因子，所以 primes[j] 也为 primes[j]*i 最小质因子
            */
        }
    }
}
int main() {
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
}

约数

试除法求一个数的所有约数

试除法求约数

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
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> get_divisors(int n) {
    vector<int> res;
    // 枚举每一对约数中较小的那个
    for(int i=1;i<=n/i;i++) {
        if(n%i==0) {
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        int a;
        cin >> a;
        auto t = get_divisors(a);
        for(auto x: t) cout << x << " ";
        cout << endl;
    }
    return 0;
}

约数个数

如果一个数 N=p1α1⋅p2α2⋯pkαkN=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \dotsm p_k^{\alpha_k}

因为每个约数可以记作 d=p1β1⋅p2β2⋯pkβkd=p_1^{\beta_1}\cdot p_2^{\beta_2} \dotsm p_k^{\beta_k}

β1,β2,…,βk\beta_1,\beta_2,\dotsc,\beta_k 是一种取法，根据乘法原理

N 的约数的个数为 (α1+1)⋅(α2+1)⋯(αk+1)(\alpha_1+1) \cdot (\alpha_2+1) \dotsm (\alpha_k+1)

int 范围内，一个数的约数最多有 1500 ~ 1600 个

约数之和

约数之和公式：(p10+p11+⋯+p1α1)⋅(p20+p21+⋯+p2α2)⋅⋯⋅(pk0+pk1+⋯+pkαk)(p_1^{0}+p_1^{1}+\dotsb+p_1^{\alpha_1}) \cdot (p_2^{0}+p_2^{1}+\dotsb+p_2^{\alpha_2}) \cdot \dots \cdot (p_k^{0}+p_k^{1}+\dotsb+p_k^{\alpha_k})

约数之和

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 <iostream>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while(n--) {
        int x;
        cin >> x;
        for(int i=2;i<=x/i;i++) {
            while(x%i==0) {
                x/=i;
                primes[i]++;
            }
        }
        if(x>1) primes[x]++;
    }
    LL res = 1;
    for(auto [p, a]: primes) {
        LL t = 1;
        while(a--) {
            t = (t*p+1)%mod;
        }
        res = (res * t)%mod;
    }
    cout << res << endl;

    return 0;
}

欧几里得算法（辗转相除法）求最大公约数

最大公约数

最小公倍数：[a, b] = a*b/(a, b)

最小公倍数 = 两数之积除以最小公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return b ? gcd(b, a%b):a;
}
int n;
int main() {
    cin >> n;
    while(n--) {
        int a, b;
        cin >> a >> b;
        cout << gcd(a,b) << endl;
    }
    return 0;
}

欧拉函数

1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)\phi(N)。

若在算数基本定理中：N=p1α1⋅p2α2⋯pkαkN=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \dotsm p_k^{\alpha_k}

欧拉函数的计算公式：ϕ(N)=N⋅(1−1p1)⋅(1−1p2)⋯(1−1pk)\phi(N)=N \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \dotsm (1 - \frac{1}{p_k})

容斥原理证明：

从 1 ~ N 中去掉所有 p1,p2,…,pkp_1, p_2, \dotsc, p_k 的倍数。
N−Np1−Np2−Np3−⋯−NpkN-\frac{N}{p_1}-\frac{N}{p_2}-\frac{N}{p_3}-\dotsb-\frac{N}{p_k}

由于去除的数可能是 p1⋅p2,…,pi⋅pj,…p_1 \cdot p_2, \dotsc, p_i \cdot p_j, \dotso 的倍数，所以要把多去除的数加回来。
+Np1⋅p2+Np1⋅p3+Np1⋅p4+⋯+Npi⋅pj+⋯+\frac{N}{p_1 \cdot p_2}+\frac{N}{p_1 \cdot p_3}+\frac{N}{p_1 \cdot p_4}+\dotsb+\frac{N}{p_i \cdot p_j}+\dotsm

同样，那些 p1⋅p2⋅p3,…,pi⋅pj⋅pk,…p_1 \cdot p_2 \cdot p_3, \dotsc, p_i \cdot p_j \cdot p_k, \dotso 同时是三个质因子倍数的数，会被第一步减去三次，又被第二步加回三次，所以需要再在这里去掉一次。
−Np1⋅p2⋅p3−Np1⋅p2⋅p4−Np1⋅p2⋅p5−⋯−Npi⋅pj⋅pk−⋯-\frac{N}{p_1 \cdot p_2 \cdot p_3}-\frac{N}{p_1 \cdot p_2 \cdot p_4}-\frac{N}{p_1 \cdot p_2 \cdot p_5}-\dotsb-\frac{N}{p_i \cdot p_j \cdot p_k}-\dotsm

⋯\dotsm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while(n--) {
        int a;
        cin >> a;
        int res = a;
        for(int i=2;i<=a/i;i++) {
        // 从2开始寻找a的质因子
            if(a%i==0) {
            // 找到一个质因子后就计算欧拉函数
                res = res /i*(i-1);
                // 把质因子除干净
                while(a%i==0) a/=i;
            }
        }
        if(a>1) res=res/a*(a-1);
        cout << res << endl;
    }
    return 0;
}

欧拉定理：若 a 与 n 互质，则 aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod {n}。

费马小定理：如果 a 与 p 互质，且 p 是质数，那么：ap−1≡1(modp)a^{p-1} \equiv 1 \pmod {p}

快速幂

快速求解 ak mod pa^{k} \bmod p 的结果。

时间复杂度 O(log⁡k)O(\log k)

快速幂求逆元

考察快速幂和小费马定理。

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
#include <iostream>
using namespace std;
typedef long long LL;
// 把指数转化成二进制然后边计算 a^(2^i) 边累乘
int pmi(int a, int k, int p) {
    // res 记录结果
    int res = 1;
    // 只要 k 没有算完
    while(k) {
        // 如果 k 的低位是 1，就将 a 乘到 res 中
        if(k&1) res = (LL)res*a%p;
        // k 右移一位
        k>>=1;
        // 计算 a^(2^i)
        a = (LL)a * a % p;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, p;
        scanf("%d%d", &a, &p);
        int res = pmi(a, p-2, p);
        if(a % p) printf("%d\n", res);
        else puts("impossible");
    }
    return 0;
}

扩展欧几里得算法

裴蜀定理：对任意正整数 a，b，一定存在非零整数 x，y 使得 ax + by = gcd(a, b)。

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}
int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, b, x ,y;
        scanf("%d%d", &a, &b);
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

线性同余方程

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
#include <iostream>
using namespace std;
typedef long long LL;
int exgcd(int a, int b, int& x, int& y) {
    if(!b) {
        x=1,y=0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}

int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b%d) puts("impossible");
        else printf("%d\n", (LL)x*(b/d)%m);
    }
}

中国剩余定理

m1,m2,…,mkm_1, m_2, \dotsc, m_k 两两互质

有线性方程组

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \vdots\\ x \equiv a_k \pmod {m_k} \end{cases}

记
M=m1⋅m2⋯mkM=m_1 \cdot m_2 \dotsm m_k
Mi=MmiM_i=\frac{M}{m_i}
Mi−1M_i^{-1} 表示 MiM_i 模 mim_i 的逆。
则通解为：x=a1⋅M1⋅M1−1+a2⋅M2⋅M2−1+⋯+ak⋅Mk⋅Mk−1x=a_1 \cdot M_1 \cdot M_1^{-1}+a_2 \cdot M_2 \cdot M_2^{-1}+\dotsb+a_k \cdot M_k \cdot M_k^{-1}