代码模板存档

标签：std return int 存档 代码 vector siz leader 模板

代码模板存档）

2022.9.30 增加并查集、埃氏筛、线性筛、快速幂、扩展欧几里得、求逆元

---

一般 C++ 比赛文件模板

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    

    return 0;
}

---

并查集

jls 的并查集模板

struct DSU{
    std::vector<int> p, siz;

    DSU(int n) : p(n), siz(n, 1) {std::iota(p.begin(), p.end(), 0); }

    int leader(int x) {
        if (x != p[x]) {
            p[x] = leader(p[x]);
        }
        return p[x];
    }

    void merge(int x, int y) {
        int px = leader(x);
        int py = leader(y);
        if (px != py) {
            siz[py] += siz[px];
            p[px] = py;
        }
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    int size(int x) {
        return siz[leader(x)];
    }
};

---

埃氏筛

std::vector<int> construct_plist(int mx) {
    std::vector<int> plist;
    std::vector<bool> fl(mx + 1, false);
    for(int i = 2; i <= mx; i++) {
        if(fl[i]) {
            continue;
        }
        plist.push_back(i);
        for(int j = i; j <= mx; j += i) {
            fl[j] = true;
        }
    }

    return plist;
}

---

线性筛

std::vector<int> conplist(int n) {
    std::vector<bool> f(n + 1, 0);
    std::vector<int> plist;
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            plist.push_back(i);
        }
        for (int j = 0; plist[j] <= n / i; j++) {
            f[plist[j] * i] = 1;
            if (i % plist[j] == 0) {
                break;
            }
        }
    }

    return plist;
}

快速幂非递归版

int quick_pow(int a, int b) {
    int ans = 1;
    while (b != 0) {
        if (b % 2 == 1) {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}

---

扩展欧几里得

求形如 \(a \equiv 1 \ (mod \ m)\)

(待补充)

int exgcd(int a, int m, int& u, int& v) {
    if(m == 0) {
        u = 1; v = 0;
        return a;
    } else {
        int x1;
        int d = exgcd(m, a % m, x1, u);
        v = x1 - a / m * u;
        return d;
    }
}

求逆元（配合exgcd）

求 \(a\) 关于 \(p\) 的逆元，即求 \(a \equiv 1 \ (mod \ p)\) 下，\(a\) 的逆元

int inv(int a, int p) {
    int u, v;
    exgcd(a, p, u, v);
    return (u % p + p) % p;
}

标签：std,return,int,存档,代码,vector,siz,leader,模板
From： https://www.cnblogs.com/isrol/p/16744688.html