List of Intergers

题目大意

求第大的大于等于 且与 互质的数

分析

即，求最小的 使：

莫比乌斯反演

那么看见这个形式，自然而然地会想到这个东西：

所以就可以把 写成：

那么交求和顺序，先枚举 的因子 ，可以得到:

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

容斥

还是考虑，换一种写法呢就是

那么就是说，不合法的就是

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

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

同样的，还是可以得到容斥系数就是

那么还是能够得到同一个式子：

当然，这并不是巧合，有兴趣的同学可以自行了解一下(我也说不清)

时间复杂度为

Code

#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：有位机房巨佬认为我写的这个是有点小问题的，我觉得这个可以解释一下

他的意思是按照样例给的，我的函数求得的和的答案都是，那么为什么我取得的是而不是，然后与并不互质，为什么对还有答案呢？

回到最开头，有这样一个东西：

会发现，我们求得的值，并不是说是第几个，我们求得的值是在有几个

令：

当时，当且仅当，所以，我们二分答案要取的是第一个满足条件的数