[poj 2773] Happy 2006 解题报告 (二分答案+容斥原理)

题目链接：http://poj.org/problem?id=2773

题目大意：

给出两个数m,k，要求求出从1开始与m互质的第k个数

题解：

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int N=1e6+;

const int inf=+;

int m,k,cnt;

int a[N],p[N];

void getprime(int x)

{

    cnt=;

    for (int i=;i*i<=x;i++)

    {

        if (x%i) continue;

        p[++cnt]=i;

        while (x%i==) x/=i;

    }

    if (x>)

    {

        p[++cnt]=x;

    }

}

int left(int x)

{

    int sum=;

    for (int i=;i<(<<cnt);i++)

    {

        int tmp=,one=;

        for (int j=;j<cnt;j++)

        {

            if (i&(<<j))

            {

                one++;

                tmp*=p[j+];

            }

        }

        if (one&)

        {

            sum+=x/tmp;

        }

        else sum-=x/tmp;

    }

    return x-sum;

}

int main()

{

    while (~scanf("%d%d",&m,&k))

    {

        getprime(m);

        int l=,r=inf,mid,ans;

        while (l<=r)

        {

            mid=l+r>>;

            int pt=left(mid);

            if (pt>=k)

            {

                if (pt==k) ans=mid;

                r=mid-;

            }

            else l=mid+;

        }

        printf("%d\n",ans);

    }

    return ;

}