分析

求第 $k$ 大的大于等于 $x$ 且与 $p$ 互质的数，那么我们先考虑如果我们枚举第 $k$ 大是谁，其实并不好做。这样时间复杂度的的下限至少为 $O(tn)$ 。那么我们考虑二分一个值 $pos$ ， $[1,pos]$ 与 $p$ 互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于 $x$ 这个条件，做一次差分就好了。那么现在算法的主要问题就是如何求出 $[1,pos]$ 有几个数与 $p$ 互质。如果我们学习过 $\varphi(p)$ ，那么我们可以很快从这里找到相似点， $\varphi(p)$ 的定义为 $[1,p-1]$ 中有几个数与 $p$ 互质。而 $\varphi(p)$ 的求解方式为 $\varphi(p)=p\prod(1-\frac{1}{P_i})$ ，我们发现并不能很好的拓展到 $[1,pos]$ ，但是我们不要忘了 $\varphi(p)$ 最根本的求解方法，容斥。 $\varphi(n) = \sum_{S\subseteq\{p_1,p_2,..p_k\}}(-1)^{|S|}\frac{n}{\prod_{p_i\in S}p_i}$ 。我们发现这个的定义其实比较简单，我们先去掉 $p_1,p_2,p_3..p_k$ 的倍数，再加上 $p_1p_2,p_1p_3..,p_{k-1}p_k$ 的倍数，因为它们被减去了两次，以此类推，枚举完所有子集，那么我们推广到 $[1,pos]$ 就比较好做了，先减去 $p_1,p_2..p_k$ 的倍数，再加上两两的倍数 $...$ 。那么只需要做一个容斥就好了。

算法

先唯一分解，将 $p$ 分解为 $P_1^{a_1}P_2^{a_2}..P_{k}^{a_k}$ 的形式。
$k$ 先加上 $[1,x]$ 的与 $p$ 互质的个数。
二分答案，这里有个小细节要处理。我们二分的答案如果已经满足了，我们要考虑更小的答案，因为当前答案可以并不与 $p$ 互质。但是个数的变化一定是一个连续的区间，所有取最小的满足的答案，才是我们要的答案。
令 $w$ 为质因子个数，时间复杂度为 $O(t\times \log p(\sqrt{p}+2^{w}))$ 。但其实 $w$ 很小，所以跑的还是挺快的。
其实上问还必须证明一个 $\lfloor \frac{\lfloor\frac{n}{a}\rfloor}{b}\rfloor = \lfloor\frac{n}{ab}\rfloor$ 想想为什么？证明放下面了，如果不明白的，欢迎私聊。

$\begin{aligned} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\ \implies &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\end{aligned}$

代码

#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;
  }
}

List of Intergers

分析

算法

代码