质(素)数

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟
Adversity does teach who your real friends are.

素数：

一个数可以表示为 那么一个数的约数个数等于它的幂加1累乘 约数个数，表示为 中与 互质的数的个数被称为欧拉函数，记为

若在算数基本定理中， ，则: 其数量级为

结论：

在int范围内：一个数的约数最多有 个

在 以内，约数个数最多有

附：

可以在 的时间复杂度中判定质数

可以分解 次方以内的质因数

练习：

模板题

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
// Miller Rabin 质数判定
#include <bits/stdc++.h> 

using i64 = long long;
template <class T>
T qpow(__int128 a, T b, T p) {
    T res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
 // O(7 * log(n))
bool MillerRabin(i64 n) {
    if (n == 2) return true;
    if (n <= 1 || n % 2 == 0) return false;
    // 这七个底数是在64位整型里一定不会出错的
    std::array<i64, 7> base {2, 235, 9375, 28178, 450775, 9780504, 1795265022};
    i64 u = n - 1, k = 0;
    while (u % 2 == 0) {
        u /= 2;
        k++;
    }
    for (auto x : base) {
        if (x % n == 0) continue ;
        i64 v = qpow(x, u, n);
        if (v == 1 || v == n - 1) continue ;
        for (int j = 1; j <= k; j++) {
            i64 last = v;
            v = (__int128)v * v % n;
            if (v == 1) {
                if (last != n - 1) return false;
                break;
            }
        }
        if (v != 1) return false;
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 n;
    while (std::cin >> n) {
        std::cout << (MillerRabin(n) ? "Y\n" : "N\n");
    }
    
    return 0;
}

模板题

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
103
104
105
106
107
108
109
110
// Pollard Rho 分解质因数
#include <bits/stdc++.h> 

using i64 = long long;
template <class T>
T qpow(__int128 a, T b, T p) {
    T res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
 // O(7 * log(n))
bool MillerRabin(i64 n) {
    if (n == 2) return true;
    if (n <= 1 || n % 2 == 0) return false;
    // 这七个底数是在64位整型里一定不会出错的
    std::array<i64, 7> base {2, 235, 9375, 28178, 450775, 9780504, 1795265022};
    i64 u = n - 1, k = 0;
    while (u % 2 == 0) {
        u /= 2;
        k++;
    }
    for (auto x : base) {
        if (x % n == 0) continue ;
        i64 v = qpow(x, u, n);
        if (v == 1 || v == n - 1) continue ;
        for (int j = 1; j <= k; j++) {
            i64 last = v;
            v = (__int128)v * v % n;
            if (v == 1) {
                if (last != n - 1) return false;
                break;
            }
        }
        if (v != 1) return false;
    }
    return true;
}

i64 Pollard_Rho(i64 n) {
    static std::mt19937_64 sj(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<i64> u0(1, n - 1);

    i64 c = u0(sj);
    auto f = [&](i64 x) {
        return ((__int128)x * x + c) % n;
    };
    i64 x = 0, y = 0, s = 1;
    for (int k = 1; ; k <<= 1, y = x, s = 1) {
        for (int i = 1; i <= k; i++) {
            x = f(x);
            s = (__int128)s * abs(x - y) % n;
            if (i % 127 == 0) {
                i64 d = std::gcd(s, n);
                if (d > 1) return d;
            }
        }
        i64 d = std::gcd(s, n);
        if (d > 1) return d;
    }
    return n;
}

std::vector<i64> factor;
void get(i64 n) {
    if (n == 1) return ;
    if (MillerRabin(n)) {
        factor.push_back(n);
        return ;
    }

    i64 x = n;
    while (x == n) x = Pollard_Rho(n);
    get(x), get(n / x);
}

void solve() {
    i64 n;
    std::cin >> n;

    if (n == 1) {
        std::cout << "0\n";
        return ;
    }
    factor.clear();
    get(n);
    std::sort(factor.begin(), factor.end());
    std::cout << factor.size() << " ";
    for (auto x : factor) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

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

    while (t--) {
        solve();
    }
    
    return 0;
}

练习：

例题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
#include <bits/stdc++.h> 

using i64 = long long;

constexpr int N = 1E6 + 10;
int cnt[N];

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        cnt[a[i]]++;//每个数出现的个数
    }

    std::vector<int> ans(N);
    //这两个循环一共O（Nlog(N)）
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {//这个因子在当前j这个数的贡献+1
            ans[j] += cnt[i];//
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[a[i]] - 1 << "\n";
    }    
    return 0;
}

例题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
41
#include <bits/stdc++.h> 

using i64 = long long;

constexpr int P = 1E9 + 7, N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}   

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

    init(n);

    int res = 1;
    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int s = 0;
        for (int j = n; j; j /= p) {
            s += j / p;
        }
        res = 1LL * res * (2 * s + 1) % P;
    }
    std::cout << res << "\n";

    return 0;
}

例题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
#include <bits/stdc++.h> 

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::array<int, 9> primes {2, 3, 5, 7, 11, 13, 17, 19, 23};

    int n;
    std::cin >> n;
    
    // 最大约数个数  数本身这个数
    int maxd = 0, number = 0;
    //           第几个质数   数最大    乘积    约数个数  
    std::function<void(int, int, int, int)> dfs = [&](int u, int last, int p, int s) {
        if (s > maxd || s == maxd && p < number) {
            maxd = s;
            number = p;
        }
        // 表示枚举到所有情况了
        if (u == 9) return ;
        // 枚举次数，从第一次开始枚举，最多枚举30次
        // 因为 2^30 大概是 2e9
        for (int i = 1; i <= last; i++) {
            if ((i64)p * primes[u] > n) break;
            p *= primes[u];
            dfs(u + 1, i, p, s * (i + 1));
        }
    };

    dfs(0, 30, 1, 1);

    std::cout << number << "\n";
    
    return 0;
}

例题4：Hankson的趣味题

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
#include <bits/stdc++.h> 

using i64 = long long;

void solve() {
    int a0, a1, b0, b1;
    std::cin >> a0 >> a1 >> b0 >> b1;

    int t = b1;

    std::vector<int> a(1, 1);
    for (int i = 2; i <= b1 / i; i++) {
        if (b1 % i == 0) {
            a.push_back(i);
            if (i != b1 / i) a.push_back(b1 / i);
        }
    }
    if (a[0] != t) a.push_back(t);
    
    auto check = [&](int x) {
        return std::gcd(x, a0) == a1 && std::lcm(x, b0) == t;
    };

    int res = 0;
    for (int i : a) {
        if (check(i)) {
            res++;
        }
    }
    std::cout << res << "\n";
}

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

    while (t--) {
        solve();
    }
    
    return 0;
}

欧拉函数：

中与 互质的数的个数被称为欧拉函数，记为

若在算数基本定理中， ，则:

结论：

如果 是 的最小质因子： 可以得到： 平面上两个点的坐标互质，那么它们到达原点才不会经过其他点到原点的连线

练习：

例题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
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100010;
int phi[N], primes[N];
bool st[N];
int tot;

int get_eulers(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; i * primes[j] <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += phi[i];
    }
    return res;
}

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

    int C;
    std::cin >> C;

    for (int i = 1; i <= C; i++) {
        int N;
        std::cin >> N;

        std::cout << i << " " << N << " " << get_eulers(N) * 2 + 1 << "\n";
    }

    return 0;
}

例题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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h> 

using i64 = long long;

constexpr int N = 1E7 + 10;
int phi[N], primes[N];
bool st[N];
int tot;

i64 s[N];
void init(int n) { // O(n)
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot && i * primes[j] <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    for (int i = 2; i <= N; i++) {
        s[i] = s[i - 1] + phi[i];
    }
}

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

    init(N);
    
    i64 res = 0;
    for (int i = 0; i < tot; i++) {
        int p = primes[i];
        res += s[N / p] * 2 + 1;
    }
    std::cout << res << "\n";
    
    return 0;
}