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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;

// 判断质数
bool ispr(int n) {
    if (n < 2) return 0;
    for (int i = 2; i <= n/i; i++)
        if (n % i == 0) return 0;
    return 1;
}

// 筛质数(埃筛)
bool v[N]; // v存合数标记
void pr(int n) {
    memset(v, 0, sizeof v);
    for (int i = 2; i <= n; i++) {
        if (v[i]) continue;
        cout << i << '\n';
        for (int j = i; j <= n/i; j++) v[i * j] = 1;
    }
}

// 线性筛
int v[N], pr[N], m; // v存最小质因子
void pr(int n) {
    memset(v, 0, sizeof v);
    m = 0;
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) {
            v[i] = i;
            pr[++m] = i;
        }

        for (int j = 1; j <= m; j++) {
            // i有比pr[j]更小的质因子，或者超出n的范围，跳出循环
            if (pr[j] > v[i] || pr[j] > n/i) break;

            v[i * pr[j]] = pr[j];
        }
    }
    for (int i = 1; i <= m; i++) cout << pr[i] << '\n';
}

// 质因数分解
int p[N], c[N], m;
void divide(int n) {
    m = 0;
    for (int i = 2; i <= n/i; i++) {
        if (n % i == 0) {
            p[++m] = i, c[m] = 0;
            while (n % i == 0) n /= i, c[m]++;
        }
    }
    if (n > 1)
        p[++m] = n, c[m] = 1;
    for (int i = 1; i <= m; i++)
        cout << p[i] << '^' << c[i] << '\n';
}

// 试除法求N的约数集合
int fac[1600], m = 0;
for (int i = 1; i <= n/i; i++) {
    if (n % i == 0) {
        fac[++m] = i;
        if (i != n/i) fac[++m] = n/i;
    }

    for (int i = 1; i <= m; i++) cout << fac[i] << '\n';
}

// 倍数法求1~N每个数的正约数集合
vector<int> fac[500010];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n/i; j++)
        fac[i * j].push_back(i);
for (int i = 1; i <= n; i++) {
    for (int j = 0; j < fac[i].size(); j++)
        printf("%d ", fac[i][j]);
    puts("");
}

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

// 求最小公倍数
int lcm(int x, int y) {
    return (x * y) / gcd(x, y);
}

// 快速幂
typedef long long ll;
ll quick_pow(ll x, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return res;
}