发表更新基础 / 模板17 分钟读完 (大约2511个字)

图论

本文内容参考《算法》，《算法导论》，OI Wiki。

拓扑排序

例题

实现

  • 时间复杂度为 \(O(n+m)\)。
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
private static int[] topologicalSort(int n, int[][] edges) {
    int[] in = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1];
        g[u].add(v);
        in[v]++;
    }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
        }
    }

    int idx = 0;
    int[] res = new int[n];
    while (!q.isEmpty()) {
        int x = q.poll();
        res[idx++] = x;
        for (int y : g[x]) {
            if (--in[y] == 0) {
                q.offer(y);
            }
        }
    }

    // 拓扑排序不存在
    assert idx == n;

    return res;
}

最小生成树

例题

Prim

实现一：朴素版本

  • 时间复杂度为 \(O(n^{2})\)。
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
private static int prim(int n, int[][] edges) {
    int[][] g = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(g[i], Integer.MAX_VALUE);
        g[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (g[u][v] > w) {
            g[u][v] = g[v][u] = w;
        }
    }

    int[] d = new int[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    boolean[] vis = new boolean[n];

    int res = 0;
    d[0] = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (t == -1 || d[t] > d[j])) {
                t = j;
            }
        }

        // 不是连通图，最小生成树不存在
        assert d[t] != Integer.MAX_VALUE;

        vis[t] = true;
        res += d[t];

        for (int j = 0; j < n; j++) {
            d[j] = Math.min(d[j], g[t][j]);
        }
    }

    return res;
}

实现二：优先队列优化

  • 时间复杂度为 \(O(m\log{m})\)。
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
private static int prim(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
        g[v].add(new int[]{u, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    boolean[] vis = new boolean[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    int res = 0, cnt = 0;
    d[0] = 0;
    q.offer(new int[]{0, 0});
    while (!q.isEmpty()) {
        int u = q.poll()[0];
        if (vis[u]) continue;
        vis[u] = true;
        res += d[u];
        if (++cnt == n) break;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (!vis[v] && d[v] > w) {
                d[v] = w;
                q.offer(new int[]{v, d[v]});
            }
        }
    }

    // 不是连通图，最小生成树不存在
    assert cnt == n;

    return res;
}

Kruskal

  • 时间复杂度为 \(O(m\log{m})\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);

    int cnt = 1, res = 0;
    UnionFind uf = new UnionFind(n);
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (uf.connected(u, v)) continue;
        uf.union(u, v);
        res += w;
        if (++cnt == n) break;
    }

    // 不是连通图，最小生成树不存在
    assert cnt == n;

    return res;
}

最短路

例题

Dijkstra

  • 使用场景：解决边权非负的单源最短路问题。

实现一：朴素版本

  • 时间复杂度为 \(O(n^{2})\)。
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
private static final int INF = (int) 1e9;

private static int dijkstra(int n, int[][] edges) {
    int[][] g = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(g[i], INF);
        g[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u][v] = Math.min(g[u][v], w);
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    boolean[] vis = new boolean[n];

    d[0] = 0;
    while (true) {
        int t = -1;
        for (int i = 0; i < n; i++) {
            if (!vis[i] && (t == -1 || d[t] > d[i])) {
                t = i;
            }
        }

        if (t == n - 1 || d[t] == INF) {
            break;
        }
        vis[t] = true;

        for (int i = 0; i < n; i++) {
            d[i] = Math.min(d[i], d[t] + g[t][i]);
        }
    }

    return d[n - 1] == INF ? -1 : d[n - 1];
}

实现二：优先队列优化

  • 时间复杂度为 \(O(m\log{m})\)。
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
private static final int INF = (int) 1e9;

private static int dijkstra(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    boolean[] vis = new boolean[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    d[0] = 0;
    q.offer(new int[]{0, 0});
    while (!q.isEmpty()) {
        int u = q.poll()[0];
        if (u == n - 1) break;
        if (vis[u]) continue;
        vis[u] = true;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.offer(new int[]{v, d[v]});
            }
        }
    }

    return d[n - 1] == INF ? -1 : d[n - 1];
}

Bellman-Ford

  • 时间复杂度为 \(O(nm)\)。
  • 使用场景：解决任意边权的单源最短路问题；判断是否存在负环；解决有边数限制的单源最短路问题。

实现一：朴素版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static final int INF = (int) 1e9;

private static int bellmanFord(int n, int[][] edges) {
    int[] d = new int[n];
    Arrays.fill(d, INF);

    d[0] = 0;
    for (int i = 0; i < n; i++) {
        for (var e : edges) {
            int u = e[0], v = e[1], w = e[2];
            d[v] = Math.min(d[v], d[u] + w);
        }
    }

    // d[n - 1] == INF 时，最短路不存在
    return d[n - 1];
}

实现二：队列优化（不能存在负环）

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
private static final int INF = (int) 1e9;

private static int spfa(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    Queue<Integer> q = new ArrayDeque<>();
    boolean[] on = new boolean[n];

    d[0] = 0;
    q.offer(0);
    on[0] = true;
    while (!q.isEmpty()) {
        int u = q.poll();
        on[u] = false;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (!on[v]) {
                    q.offer(v);
                    on[v] = true;
                }
            }
        }
    }

    // d[n - 1] == INF 时，最短路不存在
    return d[n - 1];
}

Floyd-Warshall

  • 时间复杂度为 \(O(n^{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
private static final int INF = (int) 1e9;

private static int[][] floyd(int n, int[][] edges) {
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], INF);
        dp[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        dp[u][v] = Math.min(dp[u][v], w);
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][k] != INF && dp[k][j] != INF) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    return dp;
}

最近公共祖先

例题

倍增

  • 预处理时间复杂度为 \(O(n\log{n})\)，查询时间复杂度为 \(O(\log{n})\)。
  • 原理：\(f[i][j]\) 表示节点 \(j\) 的第 \(2^{i}\) 个祖先，当利用倍增得到 \(f\) 时，对于任意两个节点 \(x,y\)，先将较深的节点向上跳到相同深度，然后两个节点贪心的向上跳到 \(\operatorname{lca}\) 下方距离它最近的节点，最后得到的节点就是 \(\operatorname{lca}\) 的直接子节点。（在进行倍增时，根节点的父节点可以是任何值，因为该值不会影响算法的正确性）
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
private static void dfs(int x, int fa, List<Integer>[] g, int[][] f, int[] d) {
    f[0][x] = fa;
    for (int i = 1; 1 << i <= d[x]; i++) {
        f[i][x] = f[i - 1][f[i - 1][x]];
    }
    for (int y : g[x]) {
        if (y != fa) {
            d[y] = d[x] + 1;
            dfs(y, x, g, f, d);
        }
    }
}

private static int lca(int x, int y, int[][] f, int[] d) {
    if (d[x] > d[y]) {
        int t = x; x = y; y = t;
    }

    int diff = d[y] - d[x];
    for (int i = 0; i < 31; i++) {
        if ((diff >> i & 1) == 1) {
            y = f[i][y];
        }
    }

    if (x != y) {
        for (int i = 30; i >= 0; i--) {
            if (f[i][x] != f[i][y]) {
                x = f[i][x];
                y = f[i][y];
            }
        }
        x = f[0][x];
    }
    return x;
}

Tarjan

  • 离线查询算法，时间复杂度为 \(O((n+m)\log{n})\)。更精确的复杂度分析可以使用反阿克曼函数。
  • 原理：每当处理完一个子树，就将该子树的根节点和其父节点合并，特别注意合并的方向是 \(f[y]=x\)。然后我们会遍历包含当前节点 \(x\) 的查询，如果另一个节点 \(y\) 访问过，则 \(\operatorname{lca}(x,y)=\operatorname{find}(y)\)。至于为什么是这样，可以通过分类讨论得到。注意 \(q\) 需要像无向图一样，为单个查询存储双向边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void tarjan(int x, List<Integer>[] g, boolean[] vis, UnionFind uf, List<int[]>[] q, int[] ans) {
    vis[x] = true;
    for (int y : g[x]) {
        if (!vis[y]) {
            tarjan(y, g, vis, uf, q, ans);
            uf.union(x, y); // 注意 f[y] = x
        }
    }

    for (int[] t : q[x]) {
        int y = t[0], i = t[1];
        if (vis[y]) {
            ans[i] = uf.find(y);
        }
    }
}

树链剖分

  • 预处理时间复杂度为 \(O(n)\)，查询时间复杂度为 \(O(\log{n})\)。
  • 原理：将树划分为若干重链，树中的每条路径不会包含超过 \(\log{n}\) 条不同的重链，所以查询的时间复杂度为 \(O(\log{n})\)。第一次 DFS 得到每个节点的父节点，深度，以及根据子树大小得到每个节点的重子节点。第二次 DFS 通过优先遍历重子节点，再遍历轻子节点，从而得到每个节点所在重链的头节点。然后就可以进行查询，通过比较 \(x,y\) 所在重链的头节点，来向上跳跃，最终得到 \(\operatorname{lca}\)。
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
private static void dfs1(int x, int fa, List<Integer>[] g, int[] f, int[] d, int[] s, int[] h) {
    f[x] = fa;
    s[x] = 1; h[x] = -1;
    for (int y : g[x]) {
        if (y != fa) {
            d[y] = d[x] + 1;
            dfs1(y, x, g, f, d, s, h);
            s[x] += s[y];
            if (h[x] == -1 || s[h[x]] < s[y]) {
                h[x] = y;
            }
        }
    }
}

private static void dfs2(int x, int head, List<Integer>[] g, int[] f, int[] h, int[] t) {
    t[x] = head;
    if (h[x] == -1) {
        return;
    }
    dfs2(h[x], head, g, f, h, t);
    for (int y : g[x]) {
        if (y != f[x] && y != h[x]) {
            dfs2(y, y, g, f, h, t);
        }
    }
}

private static int lca(int x, int y, int[] f, int[] d, int[] t) {
    while (t[x] != t[y]) {
        if (d[t[x]] > d[t[y]]) {
            x = f[t[x]];
        } else {
            y = f[t[y]];
        }
    }
    return d[x] < d[y] ? x : y;
}

强连通分量

例题

Tarjan

  • 时间复杂度为 \(O(n+m)\)。
  • 原理：\(dfn[x]\) 表示节点 \(x\) 的 DFS 编号；\(low[x]\) 表示节点 \(x\) 能够到达的节点的最小的 DFS 编号。我们将图看作一棵树，并定义四种边，那么强连通分量的根节点就是该分量中第一个被遍历到的节点，满足 \(dfn[x]=low[x]\)，所以，过程很复杂，难以描述，直接看 wiki 吧。（注意使用的时候，将 \(dfn\) 初始化为 \(-1\)，并且对所有节点调用该算法前，需要判断 \(dfn=-1\) 是否成立）
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
private static int dfnCnt, sccCnt;

private static void tarjan(int x, List<Integer>[] g, int[] dfn, int[] low, Deque<Integer> stk, boolean[] on, int[] scc, int[] size) {
    dfn[x] = low[x] = dfnCnt++;
    stk.push(x);
    on[x] = true;

    for (int y : g[x]) {
        if (dfn[y] == -1) {
            tarjan(y, g, dfn, low, stk, on, scc, size);
            low[x] = Math.min(low[x], low[y]);
        } else if (on[y]) {
            low[x] = Math.min(low[x], dfn[y]);
        }
    }

    if (dfn[x] == low[x]) {
        for (int y = -1; y != x; ) {
            y = stk.pop();
            on[y] = false;
            scc[y] = sccCnt;
            size[sccCnt]++;
        }
        sccCnt++;
    }
}
发表更新基础 / 模板6 分钟读完 (大约826个字)

数据结构

本文内容参考 OI Wiki。

并查集

例题

实现

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
class UnionFind {
    private final int[] f, s;
    private int c;

    public UnionFind(int n) {
        c = n;
        f = new int[n];
        s = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
            s[i] = 1;
        }
    }

    public int find(int x) {
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        f[ry] = rx;
        s[rx] += s[ry];
        c--;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int size(int x) {
        return s[find(x)];
    }

    public int count() {
        return c;
    }
}

树状数组

例题

实现

单点修改，区间查询

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
class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    public void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public long sum(int x) {
        long res = 0;
        for (; x > 0; x &= x - 1) {
            res += t[x];
        }
        return res;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

区间修改，单点查询

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
class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    private void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long res = 0L;
        for (int i = x; i > 0; i &= i - 1) {
            res += t[i];
        }
        return res;
    }

    public long get(int x) {
        return sum(x);
    }
}

区间修改，区间查询

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
class BIT {
    private final int n;
    private final long[] t1, t2;

    public BIT(int n) {
        this.n = n;
        t1 = new long[n + 1];
        t2 = new long[n + 1];
    }

    private void add(int i, int k) {
        long p = (long) k * i;
        for (; i <= n; i += i & -i) {
            t1[i] += k;
            t2[i] += p;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long s1 = 0, s2 = 0;
        for (int i = x; i > 0; i &= i - 1) {
            s1 += t1[i];
            s2 += t2[i];
        }
        return s1 * (x + 1) - s2;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

线段树

例题

实现

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
class SegmentTree {
    private final int n;
    private final long[] t, z;

    public SegmentTree(int[] a) {
        n = a.length;
        t = new long[4 * n];
        z = new long[4 * n];
        build(a, 1, 1, n);
    }

    private void build(int[] a, int i, int l, int r) {
        if (l == r) {
            t[i] = a[l - 1];
            return;
        }
        int mid = l + (r - l) / 2;
        build(a, 2 * i, l, mid);
        build(a, 2 * i + 1, mid + 1, r);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    private void lazy(int i, int lo, int hi, long k) {
        t[i] += k * (hi - lo + 1);
        z[i] += k;
    }

    private void down(int i, int lo, int hi) {
        if (z[i] == 0) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        lazy(2 * i, lo, mid, z[i]);
        lazy(2 * i + 1, mid + 1, hi, z[i]);
        z[i] = 0;
    }

    public void add(int l, int r, int k) {
        if (l > r) return;
        add(1, 1, n, l, r, k);
    }

    private void add(int i, int lo, int hi, int l, int r, int k) {
        if (lo >= l && hi <= r) {
            lazy(i, lo, hi, k);
            return;
        }
        down(i, lo, hi);
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) add(2 * i, lo, mid, l, r, k);
        if (r > mid) add(2 * i + 1, mid + 1, hi, l, r, k);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    public long get(int l, int r) {
        if (l > r) return 0L;
        return get(1, 1, n, l, r);
    }

    private long get(int i, int lo, int hi, int l, int r) {
        if (lo >= l && hi <= r) {
            return t[i];
        }
        down(i, lo, hi);
        long res = 0L;
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) res += get(2 * i, lo, mid, l, r);
        if (r > mid) res += get(2 * i + 1, mid + 1, hi, l, r);
        return res;
    }
}

稀疏表（Sparse Table）

例题

实现

1
System.out.println("TODO");
发表更新基础 / 模板10 分钟读完 (大约1439个字)

数学

本文内容参考《算法导论》，OI Wiki。（数学好难，暂时搁置）

快速幂

例题

整数

时间复杂度：\(O(\log{n})\)。

1
2
3
4
5
6
7
8
9
10
11
private static final long MOD = 1_000_000_007;

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}

矩阵

时间复杂度：\(O(\log{n})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static final int MOD = 1_000_000_007;

private static long[][] pow(long[][] x, long n) {
    long[][] res = {{1, 0}, {0, 1}};
    for (; n != 0; x = mul(x, x), n >>= 1) {
        if ((n & 1) == 1) {
            res = mul(res, x);
        }
    }
    return res;
}

private static long[][] mul(long[][] a, long[][] b) {
    long[][] c = new long[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

数论

例题

判断质数

时间复杂度 \(O(n\sqrt{n})\)。

1
2
3
4
5
6
7
private static boolean isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

质数筛法

埃氏筛

时间复杂度 \(O(n\log{\log{n}})\)，筛掉质数的倍数，每个合数都会被筛它的质因数的个数次。

1
2
3
4
5
6
7
8
9
10
11
12
private static boolean[] sieveOfEratosthenes(int n) {
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n / i; i++) {
        if (np[i]) continue;
        for (int j = i; j <= n / i; j++) {
            np[j * i] = true;
        }
    }
    return np;
}

欧拉筛

时间复杂度 \(O(n)\)，每个合数都只被它的最小质因数筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static boolean[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n; i++) {
        if (!np[i]) p[cnt++] = i;
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
    return np;
}

分解质因数

时间复杂度 \(O(\sqrt{n})\)。

1
2
3
4
5
6
7
8
9
10
11
private static Map<Integer, Integer> primeFactors(int x) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            x /= i;
            map.merge(i, 1, Integer::sum);
        }
    }
    if (x > 1) map.merge(x, 1, Integer::sum);
    return map;
}

欧拉函数

欧拉函数 \(\phi(n)\)，表示 \([1,n]\) 范围内和 \(n\) 互质的数的个数，有如下性质：

  • 若 \(\gcd(a,b)=1\)，则 \(\phi(a\times b)=\phi(a)\times \phi(b)\)。
  • 若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，其中 \(p_{i}\) 为质数，则 \(\phi(n)=n\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})\)。

我们可以使用分解质因数求解某个数的欧拉函数，时间复杂度为 \(O(\sqrt{n})\)；也可以使用欧拉筛来求解 \([1,n]\) 范围内所有数的欧拉函数，时间复杂度为 \(O(n)\)。在欧拉筛中，每个合数都是被它的最小质因子筛掉，设 \(p\) 是 \(n\) 的最小质因子，则 \(n=n^{\prime}\times p\)，分类讨论：

  • 如果 \(n^{\prime}\bmod p\neq 0\)，因为 \(p\) 是质数，所以 \(\gcd(n^{\prime},p)=1\)，则 \(\phi(n)=\phi(n^{\prime})\times \phi(p)=\phi(n^{\prime})\times (p-1)\)。
  • 如果 \(n^{\prime}\bmod p=0\)，则 \(\phi(n)=p\times n^{\prime}\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})=p\times \phi(n^{\prime})\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static int[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    int[] phi = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    phi[1] = 1;
    np[0] = np[1] = true;

    for (int i = 2; i <= n; i++) {
        if (!np[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) {
                phi[p[j] * i] = p[j] * phi[i];
                break;
            }
            phi[p[j] * i] = (p[j] - 1) * phi[i];
        }
    }
    return phi;
}

最大公约数

欧几里得算法

时间复杂度 \(O(\log{\max(a,b)})\)。求得最大公约数之后，使用 \(\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b\) 公式可以得到最小公倍数。

1
2
3
4
private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

扩展欧几里得算法

常用于求解 \(ax+by=\gcd(a,b)\) 的一组解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int x, y;

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

其他知识

约数个数

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(d_{n}=\prod_{i=1}^{k}(c_{i}+1)\)。

约数之和

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(s_{n}=\prod_{i=1}^{k}\sum_{j=0}^{c_{i}}{p_{i}^{j}}\)。

裴蜀定理

若 \(a,b\) 是整数，则对于任意的整数 \(x,y\)，\(ax+by\) 总是 \(\gcd(a,b)\) 的倍数，并且存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\)。特别的，若存在整数 \(x,y\) 使得 \(ax+by=1\)，则 \(\gcd(a,b)=1\)，即 \(a,b\) 互质。

费马小定理

若 \(p\) 是质数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1\pmod{p}\)。

欧拉定理

若 \(\gcd(a,n)=1\)，则 \(a^{\phi(n)}\equiv 1\pmod{n}\)。

模乘法逆元

若 \(p\) 是质数，根据费马小定理，有 \(a\times a^{-1}\equiv 1\equiv a^{p-1}\pmod{p}\)，得到 \(a^{-1}\equiv a^{p-2}\pmod{p}\)。

若 \(b\) 是任意整数，求 \(a\) 的逆元，等价于求 \(ax\equiv 1\pmod{b}\) 的解，等价于求 \(ax+by=1\) 的解。如果 \(\gcd(a,b)=1\)，则可以使用扩展欧几里得算法求解该方程。如果 \(\gcd(a,b)\neq 1\)，根据裴蜀定理可知方程无解（或者可以将方程变换为 \(\frac{a}{g}x+\frac{b}{g}y=\frac{1}{g}\)，等式左边是整数，右边不是整数，方程无解），即逆元不存在。

线性同余方程

求 \(ax\equiv c\pmod{b}\) 的解，等价于求 \(ax+by=c\) 的解，同样的，当 \(\gcd(a,b)\mid c\) 时方程有解。使用扩展欧几里得算法可以求出 \(ax+by=\gcd(a,b)\) 的解，然后将方程变换为 \(a\frac{c}{\gcd(a,b)}x_{0}+b\frac{c}{\gcd(a,b)}y_{0}=c\)，可以得到方程的解。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×