以下全都是一起参加ACM的队友的代码，我自己写的全都因为电脑重装系统没了，感谢队友。:innocent::pray:

打表

分为离线打表和在线打表，看oj平台和比赛要求吧，一般都是在线打，除非计算量很大的就离线打。

看了下代码，好像用的蛮多的都是关于素数的，用到欧拉筛。

动态规划

推荐：【宫水三叶】深度讲解背包问题

dp

树上dp

状压dp

搜索树

用得差不多，DFS多一点

BFS

DFS

并查集

单调栈与单调队列

前缀与差分

。。。

备注：

感觉往下的用的都很少了，只针对特别的题目有用，有兴趣的自行查阅

分块算法

吉司机线段树

维护区间最大值mx，区间中最大值出现次数tot，区间中的次大值se，区间和sum

扩展欧几里得与逆元

模线性方程组

欧拉函数

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
typedef long long ll;
#define N 1000100

ll phi[N], d[N];
void ini() //欧拉筛打表
{
    memset(isPrime, true, sizeof(isPrime));
    int i, j;
    for (i = 2; i < N; i++) {
        if (isPrime[i])
            prime[cnt++] = i, phi[i] = i - 1;
        for (j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = 0;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    j = 2;
    for (i = 1; i < 1000003; i++) {
        if (phi[j] >= i)
            d[i] = j;
        else
            j++, i--;
    }
}

区间与环形dp

生成树

最短路

LCA

Miller_rabin和Rollard rho

大数乘和大数幂作为基础函数

Miller_rabin

判断一个数是否是素数，好像是99.99%的正确率？

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
ll quick_mul(ll a, ll b, ll m = mod)
{
    ll ret = 0;
    while (b) {
        if (b & 1)
            ret = (ret + a) % m;
        b >>= 1;
        a = (a << 1) % m;
    }
    return ret;
}

ll quick_pow(ll a, ll b, ll m = mod)
{
    ll ret = 1;
    while (b) {
        if (b & 1)
            ret = quick_mul(ret, a, m);
        b >>= 1;
        a = quick_mul(a, a, m);
    }
    return ret;
}

bool Miller_Rabin(ll p)
{
    ll n = 0, m = p - 1;
    if (p == 2)
        return true;
    if (p < 2 || !(p & 1))
        return false;
    while (!(m & 1))
        n++, m >>= 1;
    for (int i = 0; i < 10; i++) {
        ll x = rand() % (p - 1) + 1;
        // if (quick_pow(x, p - 1, p) != 1)
        //     return false;
        x = quick_pow(x, m, p);
        for (int j = 0; j < n; j++) {
            ll x1 = quick_mul(x, x, p);
            if (x1 == 1 && x != 1 && x != p - 1)
                return false;
            x = x1;
        }
        if (x != 1)
            return false;
    }
    return true;
}

Pollard rho

快速找到大整数的一个非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
ll quick_mul(ll a, ll b, ll m = mod)
{
    ll ret = 0;
    while (b) {
        if (b & 1)
            ret = (ret + a) % m;
        b >>= 1;
        a = (a << 1) % m;
    }
    return ret;
}

ll quick_pow(ll a, ll b, ll m = mod)
{
    ll ret = 1;
    while (b) {
        if (b & 1)
            ret = quick_mul(ret, a, m);
        b >>= 1;
        a = quick_mul(a, a, m);
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

ll f(ll x, ll c, ll n)
{
    return (quick_mul(x, x, n) + c) % n;
}
ll Pollard_Rho(ll n)
{
    if (n == 4)
        return 2;
    ll f1 = 0, f2 = 0;
    while (1) {
        ll c = rand() % (n - 1) + 1;
        do {
            for (int i = 0; i < 128; i++) {
                f1 = f(f1, c, n);
                f2 = f(f(f2, c, n), c, n);
                if (f1 == f2)
                    break;
                ll d = gcd(abs(f1 - f2), n);
                if (d > 1)
                    return d;
            }
        } while (f1 != f2);
    }
}

ZKW线段树

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
ll sum[N << 2], lazy[N << 2];

void build()
{
    int i;
    for (m = 1; m <= n; m <<= 1)
        ;
    for (i = 1; i <= n; i++)
        cin >> sum[m + i];
    for (i = m - 1; i; i--)
        sum[i] = sum[i << 1] + sum[(i << 1) | 1];
}

void upd(int l, int r, ll v)
{
    ll lc = 0, rc = 0, len = 1;
    for (l += m - 1, r += m + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1) {
        if (~l & 1)
            lazy[l ^ 1] += v, lc += len;
        if (r & 1)
            lazy[r ^ 1] += v, rc += len;
        sum[l >> 1] += v * lc;
        sum[r >> 1] += v * rc;
    }
    for (lc += rc, l >>= 1; l; l >>= 1)
        sum[l] += v * lc;
}

ll query(int l, int r)
{
    ll ans = 0, lc = 0, rc = 0, len = 1;
    for (l += m - 1, r += m + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1) {
        if (~l & 1)
            ans += sum[l ^ 1] + len * lazy[l ^ 1], lc += len;
        if (r & 1)
            ans += sum[r ^ 1] + len * lazy[r ^ 1], rc += len;
        ans += lc * lazy[l >> 1] + rc * lazy[r >> 1];
    }
    for (lc += rc, l >>= 1; l; l >>= 1)
        ans += lc * lazy[l];
    return ans;
}