题目链接：G. List Of Integers
题意：给你x,p,k，问你比x大的于p互质的第k个数.
题解：我们二分答案，如何判断呢，我们先的会算1~n于p互质的个数，不会的可以看这个，其他就很简单了。
#include<bits/stdc++.h> #include<set> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define ll long long #define PI 3.14159265 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define eps 1e-7 typedef unsigned long long ull; const int mod=1e9+7; const int maxn=3e5+5; const int root=1e6+7; using namespace std; int t; ll x,pp,k,tmp; vector<ll> p; void init(int n) { p.clear(); for(ll i=2;i*i<=n;i++) { if(n%i==0) { p.pb(i); while(n%i==0)n/=i; } }if(n>1)p.pb(n); } ll slove(ll r) { ll ans=0; for(ll msk=1;msk<(1<<p.size());msk++) { ll multi=1,bits=0; for(ll i=0;i<p.size();i++) { if(msk&(1<<i))++bits,multi*=p[i]; } ll cnt=r/multi; if(bits&1)ans+=cnt; else ans-=cnt; } return r-ans; } bool judge(ll m) { if(slove(m)-tmp>=k) { return true; } return false; } int main() { scanf("%d",&t); while(t--) { scanf("%lld %lld %lld",&x,&pp,&k); init(pp); ll l=x+1,r=1e12; ll ans; tmp=slove(x); while(l<=r) { ll m=(l+r)/2; if(judge(m))ans=m,r=m-1; else l=m+1; } printf("%lld ",ans); } return 0; }