首先我们都会求[1,n]与给定的p互质的个数对吧?用容斥原理,拿n-1个p的质因子+2个p的质因子...这样容斥下去即可.
题目是要求大于x第k个与p互质的数.很明显是有单调性的,我们来二分n然后ck一下,假定cnt[n]表示[1,n]与给定的p互质的个数,那么我们是要求大于x的第k个,那么我们直接拿cnt[n]-cnt[x]看他假如多了,我们就缩小r,少了就增加l...然后就没了..
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=24;
int id,pr[N],sum;
int query(int x)//查询1~x与p互质数的个数.
{
    int res=0;
    for(int i=0;i<(1<<id);i++)
    {
        int num=0,s=1;
        for(int j=0;j<id;j++)
            if(i>>j&1)  {num++;s*=pr[j+1];}
        if(num&1)   res-=x/s;//减
        else        res+=x/s;//加
    }
    return res;
}

int main()
{
    int T,x,p,k;
    scanf("%d",&T);
    while(T--)
    {
        id=0;
        scanf("%d%d%d",&x,&p,&k);
        if(p==1)    {  printf("%d\n",x+k); continue;  }
        int temp=p;
        for(int i=2;i*i<=temp;i++)
        {
            if(temp%i==0)    pr[++id]=i;
            while(temp%i==0)    temp/=i;
        }
        if(temp>1)  pr[++id]=temp;//所有质因子
        sum=query(x);
        int l=x,r=2e7,ans=2e9;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(query(mid)-sum>=k)
            {
                r=mid-1;
                ans=min(mid,ans);
            }
            else    l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}