分析

我们考虑弱化版本：对于求一定范围内与互质的数个数
那么就是

所以答案就是枚举所有的质因子，进行简单容斥即可
所以我们需要知道容斥系数
这里我们就可以利用莫比乌斯函数的另一种用途了：作为质因子的容斥系数
因为莫比乌斯函数满足

所以我们直接线性筛所有的莫比乌斯函数
再二分答案判断即可
时间复杂度：

代码

//CF920G
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=1e6+10;

int Mu[MaxN],Prime[MaxN],Cnt;
bool Jud[MaxN];
int Test,K,X,P;
int Ans;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Init() {
    Jud[1]=true;
    Mu[1]=1;
    FOR(i,2,MaxN-5) {
        if(!Jud[i]) Prime[++Cnt]=i,Mu[i]=-1;
        for(int j=1;j<=Cnt && Prime[j]*i<=MaxN-5;j++) {
            Jud[Prime[j]*i]=true;
            if(!(i%Prime[j])) {
                Mu[i*Prime[j]]=0;
                break;
            }
            Mu[i*Prime[j]]=-Mu[i];
        }
    }
}

inline int Find(int New,int Base) {
    int Res=0;
    for(int i=1;i*i<=Base;i++) {
        if(Base%i) continue;
        Res+=Mu[i]*(New/i);
        if(i!=(Base/i)) { Res+=Mu[Base/i]*(New/(Base/i)); }
    }
    return Res;
}

int main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Test;
    Init();
    while(Test--) {
        cin>>X>>P>>K;
        Ans=0;
        K+=Find(X,P);
        int L=X,R=X+10*K;
        while(L<=R) {
            int Mid=(L+R)>>1;
            if(Find(Mid,P)>=K) { R=Mid-1; Ans=Mid; }
            else { L=Mid+1; }
        }
        cout<<Ans<<endl;
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}