POJ 2773 Happy 2006 二分+容斥原理

题意：就是给你一个数n和k，求和n互质的第k个数。
思路：一道容斥原理的题目，用容斥原理我们可以求出一个范围内和n互质的数有多少个，但是不能确定第几个是多少。这时候可以用二分求出答案，因为前K+1个数内和n互质的数一定大于等于前K个数和n互质的数的个数，即随着K的增加，和n互质的数的个数是递增的。所以可以用二分求答案，由于k比较大，所以二分的上限应该足够大。二分求出后还有一个问题，因为里面有一些数是相同的，所以我们二分求出的答案不一定是第一个出现的，这时候还需要向前循环处理一下，最后就可以得到答案。
代码：
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <cmath> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
typedef long long LL; 
const int N = 1000010; 
int prime[N/2], flag[N],cntprime = 0; 
int num1[110],num2[110],cntnum; 
bool use[110]; 
LL base; 
void init(){ 
    CLR(flag,0); 
    for(int i = 2; i <= sqrt(N+0.5); ++i){ 
        if(!flag[i]){ 
          for(int j = i * 2; j <= N; j += i){ 
            flag[j] = 1; 
          } 
        } 
    } 
    for(int i = 2;i <= N; ++i){ 
      if(!flag[i]) 
          prime[cntprime++] = i; 
    } 
} 
void fun(int x){ 
    for(int i = 0; i < cntprime; ++i){ 
        if(x % prime[i] == 0){ 
          num1[cntnum++] = prime[i]; 
          while(x % prime[i] == 0){ 
            x /= prime[i]; 
          } 
        } 
    } 
} 
void dfs(int begin,int id,int cnt,LL &x){ 
    if(id == cnt){ 
      LL ans = 1; 
      for(int i = 0;i < id; ++i){ 
        ans *= num2[i]; 
      } 
      if(id % 2){ 
           x = x - base/ans; 
      } 
      else{ 
          x = x + base/ans; 
      } 
      return; 
    } 
    for(int i = begin;i < cntnum; ++i){ 
        if(!use[i]){ 
          use[i] = true; 
          num2[id] = num1[i]; 
          dfs(i,id+1,cnt,x); 
          use[i] = false; 
        } 
    } 
} 
LL cal(LL x){ 
    base = x; 
    for(int i = 1; i <= cntnum; ++i){ 
        CLR(use,false); 
        CLR(num2,0); 
        dfs(0,0,i,x); 
    } 
    return x; 
} 
LL binary_search(int n,int K){ 
    LL rp = 10000000000; 
    LL lp = 1; 
    while(lp <= rp){ 
      LL mid = lp + (rp - lp) / 2; 
      LL nummid = cal(mid); 
      if(K < nummid){ 
        rp = mid - 1; 
      } 
      else if(K > nummid){ 
        lp = mid + 1; 
      } 
      else{ 
        return mid; 
      } 
    } 
} 
int main(){ 
    //freopen("1.txt","r",stdin); 
    init(); 
    int n,K; 
    while(scanf("%d%d",&n,&K) != EOF){ 
      CLR(num1,0); 
      CLR(num2,0); 
      cntnum = 0; 
      fun(n); 
      LL ans = binary_search(n,K); 
      while(1){ 
        LL xx = cal(ans-1); 
        if(xx == K) 
            ans--; 
        else 
            break; 
      } 
      printf("%lld/n",ans); 
    } 
    return 0; 
} 

作者：wmn_wmn