[题解]List Of Integers

题目：https://ac.nowcoder.com/acm/problem/112558
题意：t次询问[x,p,k]，找出比x大且与p互质的第k个数
分析：

• 假设答案为ans，那么就是求[x+1,ans]之间恰好有k个数与p互质，同时ans刚好要与p互质；
• 范围为1e6，同时随着ans的增大与p互质个数只会越来越大，满足单调性，所以考虑二分ans；
• 关于二分的solve，我们可以求出[1,x]之间与p互质的个数，这个枚举p的因子容斥解决就行，ans也同理，接着只要判断俩者的差是否大于等于k，逼近k就行。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int M=1e6;
vector<int>prim[M+6];
void init(){
    for(int i=2;i<=M;i++){
        if(prim[i].size()==0){
            for(int j=i;j<=M;j+=i)
            prim[j].pb(i);
        }
    }
}
int solve(int x,int p){
    int n=prim[p].size();
    int res=0;
    for(int i=1;i<(1<<n);i++){///枚举p的质因子相乘子集
        int sum=1,num=0;
        for(int j=0;j<n;j++)
            if((i>>j)&1)
                sum*=prim[p][j],num++;
        int tmp=x/sum;
        ///奇加偶减（容斥原理）
        ///res为这些因子相乘能组成的数的个数（小于x）之和
        if(num&1)
            res+=tmp;
        else
            res-=tmp;
    }
    return x-res;
}
int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int x,p,k;
        scanf("%d%d%d",&x,&p,&k);
        int fir=solve(x,p);
        int l=x,r=inf,ans;
        while(l<=r){
            int midd=(l+r)>>1;
            if(solve(midd,p)-fir>=k){
                ans=midd;
                r=midd-1;
            }
            else
                l=midd+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}