DDOSvoid's Blog

2021杭电多校10 D Pty hates prime numbers

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7080

简要题意：有 $T$ 组询问，每次给定 $n$ 和 $k$，求 $[1,n]$ 中有多少数不被前 $k$​ 个素数中任何一个素数整除

$T\le 10^5,n\le 10^{18},k\le 16$​​

Solution

首先有一个经典的 $2^k$ 的容斥做法，答案即为 $(-1)^{|S|}\lfloor\frac{n}{S}\rfloor$，其中 $S$ 表示选中的集合的乘积

我们考虑将 $16$​​ 素数分成两半，前 $8$​ 个素数的乘积为 $9699690$​，根据数论知识，我们知道 $n$​ 不是集合 $S$​ 中任何一个数的倍数等价于 $n$ 对 $S$ 的 $lcm$ 取模后不是任何一个数的倍数

那么 $[1,n]$​ 的答案为 $f[9699690]\times \lfloor\frac{n}{9699690}\rfloor+f[n\bmod 9699690]$，其中 $f[i]$ 表示 $[1,i]$ 的答案，$i\in[1,9699690]$

对于后半的素数，我们直接做容斥，对于一个集合 $S$，能够得到是 $S$ 的倍数的数为 $S,2S,\cdots,\lfloor\frac{n}{S}\rfloor S$，我们再将 $1$ 到 $\lfloor\frac{n}{S}\rfloor$ 是前 $8$​ 个素数的倍数数给剔除即可

时间复杂度 $O(\sum_{i=1}^8\frac{9699690}{p_i}+T2^8)$​

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
#include <iostream>
#define ll long long 
using namespace std;

const int N = 9699690;

int p1[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
int p2[] = { 23, 29, 31, 37, 41, 43, 47, 53 };

ll n;
int k;

int opt[256], f[N + 1];
ll mul1[256], mul2[256];

void work() {
    cin >> n >> k; ll ans = 0;
    if (k <= 8) {
        int m = 1 << k;
        for (int S = 0; S < m; ++S) ans += opt[S] * n / mul1[S];
        cout << ans << "\n";
    } else {
        int m = 1 << k - 8;
        for (int S = 0; S < m; ++S) {
            ll t = n / mul2[S]; 
            ans += opt[S] * (t / N * f[N] + f[t % N]);
        } cout << ans << "\n";
    }
}

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

    for (int i = 0; i < 8; ++i)
        for (int j = p1[i]; j <= N; j += p1[i]) f[j] = 1; 
    for (int i = 1; i <= N; ++i) f[i] = (!f[i]) + f[i - 1];
    
    int m = 1 << 8;
    for (int S = 0; S < m; ++S) {
        int cnt = 0; mul1[S] = mul2[S] = 1; 
        for (int i = 0; i < 8; ++i)
            if (S >> i & 1) ++cnt, mul1[S] *= p1[i], mul2[S] *= p2[i];
        opt[S] = cnt & 1 ? -1 : 1;
    }

    int T; cin >> T; 
    while (T--) work(); 
    return 0; 
}