题目链接：

http://poj.org/problem?id=2773

题目大意：

给你两个整数N和K。找到第k个与N互素的数(互素的数从小到大排列)。当中

(1 <= m <= 1000000，1 <= K <= 100000000 )。

解题思路：

K非常大，直接从小到大枚举找出不现实，仅仅能二分答案。二分枚举[1。INF]范围内全部的数x，

找到1~x范围内与N互素的数个数。假设等于K，则就是结果。

然后考虑1~x范围内与N互素的数个数 = x - 1~x范围内与N不互素的数个数

1~x范围内与N不互素的数个数用简单的容斥定理来求就可以。

AC代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#define LL __int64

using namespace std;

const LL INF = 0xfffffff0;

int Prime[1000010],ct,N;

void Divide()

{

    ct = 0;

    int n = N;

    for(int i = 2; i <= sqrt(n*1.0); ++i)

    {

        if(n % i == 0)

        {

            Prime[ct++] = i;

            while(n % i == 0)

                n /= i;

        }

    }

    if(n != 1)

        Prime[ct++] = n;

}

LL Solve(int n)

{

    LL ans = 0;

    for(int i = 1; i < (1 << ct); ++i)

    {

        LL odd = 0;

        LL tmp = 1;

        for(int j = 0; j < ct; ++j)

        {

            if((1 << j) & i)

            {

                odd++;

                tmp *= Prime[j];

            }

        }

        if(odd & 1)

            ans += n/tmp;

        else

            ans -= n/tmp;

    }

    return n - ans;

}

int main()

{

    int K;

    while(~scanf("%d%d",&N,&K))

    {

        Divide();

        LL Left = 1, Right = INF, Mid, tmp;

        while(Left < Right) //二分答案

        {

            Mid = (Left + Right) >> 1;

            tmp = Solve(Mid);

            if(tmp >= K)

                Right = Mid;

            else

                Left = Mid + 1;

        }

        printf("%I64d\n",Left);

    }

    return 0;

}