本文转载自  JYYHH  查看原文  2018/02/05  59    code/ 容斥/ LIS/ codeforces/ for/ 二分答案/ integer/ list   收藏        

3
7 22 1
7 22 2
7 22 3

9
13
15

5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46

187
87
139
128
141


    二分+容斥就ojbk了，考虑到<=10^6的数最多有10种质因子，我们就把p质因子分解一下，然后二分第k大的满足条件的数y是多少。
需要写一个用来计算前i个数中有多少数与p互质的函数get，那么当get(y)-get(x)>=k时，更新答案并调整右边界；否则调整左边界。
之所以这么做的原因是，我们需要找到get(y)-get(x)==k的最小的y，这个y才是要求的第k大的与p互质的数。

     还有不是很明白为什么时限是5s(虽然看洛谷上好多人都是卡着时限过的)，反正我最慢的一个点也才跑了300+ms，如图


可能是因为我加了一些预处理来优化计算过程吧hhhh，请不要把我想成用循环展开什么缓存dark技巧来卡常的毒瘤人士(虽然迫不得已的时候会用一些dark卡常技巧)

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
using namespace std;
int num,d[66],f[2066],jc[2066];
int T,n,a,p,k,ci[30];
int l,r,mid,ans,now;
const int inf=1000000000;

inline void dvd(){
	num=0,n=sqrt(p+0.5);
	for(int i=2;i<=n;i++) if(!(p%i)){
		d[++num]=i;
		while(!(p%i)) p/=i;
		if(p==1) break;
	}
	
	if(p!=1) d[++num]=p;
	
	for(int S=0;S<ci[num];S++){
		jc[S]=1;
		for(int j=0;j<num;j++) if(ci[j]&S) jc[S]*=d[j+1];
	}
}

//<=x的数中有多少与p互质 
inline int get(int x){
	int an=0;
	for(int s=0;s<ci[num];s++) an+=f[s]*(x/jc[s]);
	return an;
}

int main(){
	ci[0]=1;
	for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;
	f[0]=1;
	for(int i=1;i<=2055;i++) f[i]=-f[i^(i&-i)];
	
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&a,&p,&k);
		dvd();
		l=a+1,r=inf,now=get(a);
		while(l<=r){
			mid=l+r>>1;
			if(get(mid)-now<k) l=mid+1;
			else ans=mid,r=mid-1;
		}
		
		printf("%d\n",ans);
	}
	
	return 0;
}