CF920G List of Integers

Posted on Edited on In Word count in article: 799 Reading time ≈ 3 mins.
莫反容斥好题

List of Intergers

题目大意

求第\(k\)大的大于等于 \(x\) 且与 \(p\) 互质的数

分析

即，求最小的 \(y\) 使：

\[ \sum_{i=1}^y[i\perp p]-\sum_{i=1}^x[i\perp p]=k \]

莫比乌斯反演

那么看见这个形式，自然而然地会想到这个东西：\(\mu*1=\epsilon\)

所以就可以把 \([i\perp p]\) 写成：

\[ \sum_{d|\gcd(i,p)}\mu(d) \]

那么交求和顺序，先枚举 \(p\) 的因子 \(d\)，可以得到:

\[ \begin{align*} \sum_{i=1}^y[i\perp p]&=\sum_{i=1}^y\sum_{d|\gcd(i,p)}\mu(d)\\ &=\sum_{d|p}\mu(d)\sum_{i=1}^\left\lfloor\frac y d\right\rfloor1 \\&=\sum_{d|p}\mu(d)\left\lfloor\frac y d\right\rfloor \end{align*} \]

那么，这个时候，后面这一块，已经是十分好求的了，可以直接枚举 \(\sqrt y\) 范围内 \(y\) 的因子(顺便得到 \(>\sqrt y\) )的因子，按照这个直接加就可以了

容斥

还是考虑\([i\perp p]\)，换一种写法呢就是\([\gcd(i,p)==1]\)

那么就是说，不合法的就是\(\gcd(i,p) > 1\)

那么按照套路，还是应该用总共的减去不合法的，

那么就要枚举\(p\)的每个因子对答案的贡献

同样的，还是可以得到容斥系数就是\(\mu\)

那么还是能够得到同一个式子： \[ \sum_{i=1}^y[i\perp p]=\sum_{d|p}^y\mu(d)\left\lfloor\frac y d\right\rfloor \] 当然，这并不是巧合，有兴趣的同学可以自行了解一下(我也说不清)

时间复杂度为\(O(n\log n\sqrt n)\)

Code

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

using namespace std;

typedef long long ll;
const int maxn = 1e7 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int mu[maxn], pr[maxn], cnt, line;
bool vis[maxn];

inline void Init()
{
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pr[j] < maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) mu[i * pr[j]] = -mu[i];
            else break;
        }
    }
}

inline int Query(int n, int x)
{
    int ans(0);
    for (int l = 1; l * l <= x; ++l) {
        if (x % l) continue;
        ans += mu[l] * (n / l);
        if (l * l < x) ans += mu[x / l] * (n / (x / l));
    }
    return ans;
}

signed main()
{
    Init();
    int T = __read();
    while (T--) {
        int x = __read(), p = __read(), k = __read();
        int l(1), r(1e7), ans(0);
        line = Query(x, p);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (Query(mid, p) - line >= k) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        printf ("%d\n", ans);
    }
    system("pause");
}

UPT：有位机房巨佬认为我写的这个是有点小问题的，我觉得这个可以解释一下

他的意思是按照样例给的\(7\;22\;1\)，我的\(Query\)函数求得的\(9\)和\(10\)的答案都是\(5\)，那么为什么我取得的是\(9\)而不是\(10\)，然后\(10\)与\(22\)并不互质，为什么对\(10\)还有答案呢？

回到最开头，有这样一个东西： \[ \sum_{i=1}^y[i\perp p]-\sum_{i=1}^x[i\perp p]=k \] 会发现，我们求得的值，并不是说\(y\)是第几个，我们求得的值是在\([1,y]\)有几个

令： \[ f(x)=\sum_{i=1}^x[i\perp p] \] 当\(f(y)-f(y-1)=1\)时，当且仅当\([y\perp p]=1\)，所以，我们二分答案要取的是第一个满足条件的数