TYS的博客

算法小白努力学习中

0%

素数方法

发表于 更新于

关于素数的一些方法

假设N为1e5，对1到N中所有的数做质因子分解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static constexpr int N = 1e5 + 5;
unordered_map<int, int> prime[N];
bool isp[N];
{
    memset(isp, true, sizeof(isp));
    for (int i = 2; i < N; ++i) {
        if (isp[i]) {
            for (int j = i; j < N; j += i) {
                int cur = j, cnt = 0;
                while (cur % i == 0) {
                    cur /= i;
                    ++cnt;
                }
                prime[j][i] = cnt;
                isp[j] = false;
            }
        }
    }
}

找到1到N中所有数的因数

1
2
3
4
5
6
vector<int> fact[N];
for (int i = 1; i < N; ++i) {
    for (int j = 2 * i; j < N; j += i) {
        fact[j].push_back(i);
    }
}

找到[1:m]中满足$gcd(n, p) = x$的$p$的数量。

$$
gcd(n, p) = x \\
n = a \cdot x, p = b \cdot x \\
gcd(a, b) = 1
$$
找到[1:b]中gcd(a, b) = 1中数字的数量，计算[1:b]中gcd(a, b) != 1的数量, prime[a]为a的质因数分解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int find(int a, int b) {
    int ans = 0;
    vector<int> arr;
    for (auto it : prime[a]) {
        arr.push_back(it.first);
    }
    int sz = arr.size();
    for (int i = 1; i < (1 << sz); ++i) {
        int mul = 1, sign = -1;
        for (int j = 0; j < sz; ++j) {
            if (i >> j & 1) {
                mul *= arr[j];
                sign *= -1;
            }
        }
        ans += sign * b / mul;
    }
    return b - ans;
}

例题：https://codeforces.com/problemset/problem/1139/D

其中cnt为1到m中gcd(p, x) = y的p的数量。
$$
f[x] = 1 + \frac{cnt}{m}f[y] + \frac{\frac{m}{x}}{m}f[x]
$$