List of Intergers

List Of Integers

https://ac.nowcoder.com/acm/problem/112558

分析

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

算法

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

    #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;
      }
    }
数学 文章被收录于专栏

关于多项式

全部评论

相关推荐

点赞 评论 收藏
分享
评论
3
3
分享
牛客网
牛客企业服务