数论基础

质数筛

获得 $N$ 以内的全部素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#inlcude <bits/stdc++.h>
using namespace std;
const int N = (int)(2e6 + 10);
int n, c, primes[N];
bool comp[N];

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!comp[i]) primes[c++] = i;
        for (int j = 0; 1ll * i * primes[j] <= n; j++) {
            comp[primes[j] * i] = true;
            if (i % primes[j]) break;
        }
    }
}

二次筛

当 $N$ 比较大，但是 $R - L$ 的区间长度比较小的时候，获得 $L, R$ 之内的素数

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = (int) (1e6 + 10);
int p1[N], c, l, r;
bool st[N];

void linear(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) p1[c++] = i;
        for (int j = 0; 1LL * p1[j] * i <= n; j++) {
            st[p1[j] * i] = true;
            if (i % p1[j] == 0) break;
        }
    }
}

bool f[N];
int c2, p2[N];

int main() {
    //一次性筛质数
    linear(50000);

    while (~scanf("%d%d", &l, &r)) {
        memset(f, 0, sizeof f);
        c2 = 0;

        for (int i = 0; i < c; i++) {
            LL p = p1[i];
            for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
                f[j - l] = true;
        }

        for (int i = 0; i <= r - l; i++)
            if (!f[i] && i + l >= 2)
                p2[c2++] = i + l;

        if (c2 < 2) puts("There are no adjacent primes.");
        else {
            int minp = 0, maxp = 0;
            for (int i = 0; i < c2 - 1; i++) {
                int d = p2[i + 1] - p2[i];
                if (d < p2[minp + 1] - p2[minp]) minp = i;
                if (d > p2[maxp + 1] - p2[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", p2[minp], p2[minp + 1], p2[maxp], p2[maxp + 1]);
        }
    }
    return 0;
}

快速幂

求得 $a ^ b \pmod p$ 的值

1
2
3
4
5
6
7
8
9
10
11
#inlcude <bits/stdc++.h>
using namespace std;

#define ll long long

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    a %= p;
    for (; b; a = a * a % p, b >>= 1) if (b&1) res = res * a % p;
    return res;
}

质因数分解

把一个数 $N$ 分解为若干个质数幂求和的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#inlcude <bits/stdc++.h>
using namespace std;

unordered_map<int, int> cnt;
int n;
int main() {
    cin >> n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int c = 0;
            while (n % i == 0) {
                n /= i;
                c ++;
            }
            cnt[i] = c;
        }
    }
    if (n > 1) cnt[n]++;
}

阶乘分解

把一个数 $N$ 的阶乘 $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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static final int N = (int) (1e6 + 10);
    static final int MOD = (int) (1e9 + 7);
    static int[] p = new int[N], cnt = new int[N];
    static boolean[] f = new boolean[N];
    static int n, c;

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 2; i <= n; i++) {
            if (!f[i]) p[c++] = i;
            for (int j = 0; (long) i * p[j] <= n; j++) {
                f[i * p[j]] = true;
                if (i % p[j] == 0) break;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (!f[i]) cnt[i]++;
            else {
                int t = i;
                for (int j = 2; j * j <= t; j++) {
                    if (t % j == 0) {
                        int k = 0;
                        while (t % j == 0) {
                            t /= j;
                            k++;
                        }
                        cnt[j] += k;
                    }
                }
                if (t > 1) cnt[t]++;
            }
        }

        for (int i = 2; i <= n; i++) {
            if (cnt[i] > 0) System.out.println(i + " " + cnt[i]);
        }
    }
}

约数个数

求 $N$ 以内最大公约数是素数的数对的个数

  1. $N$ 以内互质的数对的个数是 $\varphi(x)$ 函数的前缀和
  2. 枚举范围内的质数（作为题目要求的那个最大公约数 $k$）
    1. 则剩下的部分（除以选定的数的部分）任何一对互质的数都是满足条件的，可以通过上述欧拉函数前缀和求得
    2. 不互质的数都不满足条件，至少凑出来额外的因子（假设为 $m$）有 $gcd(x, y) = m * k$
    3. 因此，不重不漏
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
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static final int N = (int) (1e7 + 10);
    static final int MOD = (int) (1e9 + 7);
    static int[] primes = new int[N], f = new int[N];
    static long[] s = new long[N];
    static boolean[] comp = new boolean[N];
    static int n, c;

    public static void main(String[] args) {
        n = in.nextInt();
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!comp[i]) {
                primes[c++] = i;
                f[i] = i - 1;
            }
            for (int j = 0; (long) i * primes[j] <= n; j++) {
                comp[i * primes[j]] = true;
                if (i % primes[j] == 0) {
                    f[i * primes[j]] = f[i] * primes[j];
                    break;
                }
                f[i * primes[j]] = f[i] * (primes[j] - 1);
            }
        }
        for (int i = 2; i <= n; i++) s[i] = s[i - 1] + f[i];

        long res = 0;
        for (int i = 0; i < c; i++) {
            int k = n / primes[i];
            res += 2 * s[k] + 1;
        }
        System.out.println(res);
    }
}

欧拉函数

之前的文章有介绍过，两种求法，分别是分解质因数版本和线性筛版本

同余

同余方程

求解形如下面的方程的数值解

拓展欧几里得算法来求（相比逆元的算法限制更少）

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.*;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static long modAdd(long a, long b) {
        return ((a % P) + (b % P)) % P;
    }

    static long modTimes(long a, long b) {
        return ((a % P) * (b % P)) % P;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static Read in = new Read();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static final int N = (int) (5e6 + 5);
    static final int P = (int) (1e9 + 7);
    static long a, b, x, y;

    static void exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return;
        }
        exgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    public static void main(String[] args) {
        a = in.nextInt();
        b = in.nextInt();
        exgcd(a, b);
        out.println(x < 0 ? x + b : x);
        out.flush();
        out.close();
    }
}

组合数

杨辉三角

小数据范围，$1000$ 以内可以使用

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
62
63
64
65
66
67
68
import java.io.*;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static long modAdd(long a, long b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }

    static long modTimes(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static final int N = (int) (1e3 + 10);
    static final int MOD = (int)(1e9 + 7);
    static int n;
    static long[][] f = new long[N][N];

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j == 1) f[i][j] = i;
                else if (i == j) f[i][j] = 1;
                else f[i][j] = modAdd(f[i - 1][j], f[i - 1][j - 1]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) out.print(f[i][j] + " ");
            out.println();
            out.flush();
        }
        out.close();
    }
}

阶乘逆元

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.*;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static long modAdd(long a, long b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }

    static long modTimes(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static final int N = (int) (2e6 + 10);
    static final int MOD = (int)(1e9 + 7);
    static int n, T;
    static long[] f = new long[N], inv = new long[N];

    static long pow(long a, long b) {
        long res = 1;
        a %= MOD;
        for (; b > 0; a = modTimes(a, a), b >>= 1) if ((b&1) == 1) res = modTimes(res, a);
        return res;
    }

    static void init(int n) {
        f[0] = f[1] = inv[0] = 1;
        for (int i = 2; i <= n; i++) f[i] = modTimes(f[i - 1], i);
        inv[n] = pow(f[n], MOD - 2);
        for (int i = n - 1; i >= 1; i--) inv[i] = modTimes(inv[i + 1], i + 1);
    }

    static long comb(int n, int m) {
        if (m > n) return 0;
        return f[n] * inv[m] % MOD * inv[n - m] % MOD;
    }

    public static void main(String[] args) {
        init(2000005);
        T = in.nextInt();
        while (T-- > 0) {
            n = in.nextInt();
            m = in.nextInt();
            out.println(comb(n, m));
            out.flush();
        }
        out.close();
    }
}

逆元

费马小定理（单个求解的情况）

要求模数是素数

也即

那么在模 $p$ 意义下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MOD = (int)(1e9 + 7);

ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    for (;b;a = a * a % MOD, b >>= 1) if (b&1) res = res * a % MOD;
    return res;
}

ll inv(int x) {
    return qpow(a, MOD - 2);
}

线性打表（多个求解的情况）

要求模数是素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define ll long long
#define ED '\n'
using namespace std;

const int MOD = (int)(1e9 + 7);
const int N = (int)(3e6 + 10);
int n, inv[N];

int main() {
    cin >> n;
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
    for (int i = 1; i <= n; i++) cout << inv[i] << ED;
}

随机逆元（多个数，但是不是按照顺序的）

要求模数是素数，可以使用前缀积，因为逆元的定义就是相乘等于1（在它规定的运算意义下）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define ll long long

const int N = (int)(2e6);
const int MOD = (int)(1e9 + 7);

int n;
ll s[N], inv[N], f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    s[0] = 1;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] * a[i] % MOD;
    f[n] = qpow(s[n], MOD - 2);
    for (int i = n - 1; i >= 1; i--) f[i] = f[i + 1]*  a[i + 1] % MOD;
    for (int i = 1; i <= n; i++) inv[i] = f[i] * s[i - 1] % MOD;
}

阶乘逆元（阶乘情况下）

求 $1 \to N$ 之间每个数的阶乘在模 $p$ 意义下的逆元，可以用来求大组合数，原理和上述一致，只不过通项刚好是阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define ll long long
#define ED '\n'
using namespace std;

const int MOD = (int)(1e9 + 7);
const int N = (int)(3e6 + 10);
ll n, f[N], inv[N];

int main() {
    cin >> n;
    f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = (f[i - 1] * i) % MOD;
    inv[n] = qpow(a, MOD - 2);
    for (int i = n - 1; i >= 1; i--) inv[i] = (inv[i + 1] * (i + 1)) % MOD;
    for (int i = 1; i <= n; i++) cout << inv[i] << ED;
}