题号 NC112558
名称 List Of Integers
来源 CF920G
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

作者：@。。。201910131627798

分析

求第 大的大于等于 且与 互质的数，那么我们先考虑如果我们枚举第 大是谁，其实并不好做。这样时间复杂度的的下限至少为 。那么我们考虑二分一个值 ， 与 互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于 这个条件，做一次差分就好了。那么现在算法的主要问题就是如何求出 有几个数与 互质。如果我们学习过 ，那么我们可以很快从这里找到相似点， 的定义为 中有几个数与 互质。而 的求解方式为 ，我们发现并不能很好的拓展到 ，但是我们不要忘了 最根本的求解方法，容斥。 。我们发现这个的定义其实比较简单，我们先去掉 的倍数，再加上 的倍数，因为它们被减去了两次，以此类推，枚举完所有子集，那么我们推广到 就比较好做了，先减去 的倍数，再加上两两的倍数 。那么只需要做一个容斥就好了。

算法

• 先唯一分解，将 分解为 的形式。
• 先加上 的与 互质的个数。
• 二分答案，这里有个小细节要处理。我们二分的答案如果已经满足了，我们要考虑更小的答案，因为当前答案可以并不与 互质。但是个数的变化一定是一个连续的区间，所有取最小的满足的答案，才是我们要的答案。
• 令 为质因子个数，时间复杂度为 。但其实 很小，所以跑的还是挺快的。
• 其实上问还必须证明一个 想想为什么？证明放下面了，如果不明白的，欢迎私聊。
• 

  代码

  #include<bits/stdc++.h>
  using namespace std;
  int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
  }
  const int N = 1e6 + 100;
  int P[60];
  int Solve(int x,int a,int type) {
    if(a == P[0] + 1) {return x * type;}
    else {
        return Solve(x,a+1,type) + Solve(x/P[a],a+1,type * -1);
    }
  }
  int solve(int x) {
    return Solve(x,1,1); 
  } 
  int main() {
    int T = read();
    while(T--) {
        int limit = read(),p = read(),k = read();P[0] = 0;
        int x = p;
        for(int i = 2;i * i <= x;i++) {
            if(x % i) continue;
            P[++P[0]] = i;
            while(!(x % i)) x = x / i;
        }
        if(x > 1) P[++P[0]] = x;
        k += solve(limit);
        int l = limit + 1,r = 1e9,ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            x = solve(mid);
            if(x >= k) r = mid - 1,ans = mid;
            else l = mid + 1;
        }
        cout << ans << endl;
    }
  }

  欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

  活动奖励：

  在牛客博客中写出题解，并回复地址
  审核通过可获得（依据题目难度和题解的内容而定）

本道题目10月2日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴