这个题的意思是给你两个数m, k， 让你求出与m互质的第k个数， 设想对于一个数r，我们可以求出小于等于r与m互质的数的个数， 那么我们就可以使用二分很快的求解。 假设我们把m唯一分解 m = p1^a1 * p2^a2 * ... * pi^ai， 那么小于等于r与m互质的数中不应该有p1 p2 .. pi这些因子， 因此问题转化成求解小于等于r且不含有p1, p2 p3 .. pi因子的数的个数， 这可以使用容斥原理来接觉， 假设Ai是不含有因子Pi的数的个数那么答案就是 r - (A1+A2+ .. Ai) + (Ai并Aj i!=j) -  ... Ai = r/pi. 代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int maxn = 100000 + 10;int m, k;int pi[maxn], npi;bool vis[maxn];int prime[maxn], num;void shai(int n){    memset(vis, 0, sizeof(vis));    int m = sqrt(n+0.5);    for(int i=2; i<=m; i++) if(!vis[i])        for(int j=i*i; j<=n; j+=i) vis[j] = 1;    num = 0;    for(int i=2; i<=n; i++) if(vis[i] == 0)        prime[num++] = i;}LL check(LL r)   //求解r中与m互质的数目{    LL res = r;    for(int i=1; i<(1<
          
           >j)&1)==1) bits++, sum*=pi[j]; if(bits%2==1) res -= r/sum; else res += r/sum; } return res;}int main(){ shai(100000); while(cin>>m>>k) { npi = 0; int tp = m; for(int i=0; i
           
            =k) { res = mid; r = mid-1; } else l = mid + 1; } cout<
            
             <