[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+15;
const int inf=1000000000+15;
int m,k,cnt;
int a[N],p[N];
void getprime(int x)
{
    cnt=0;
    for (int i=2;i*i<=x;i++)
    {
        if (x%i) continue;
        p[++cnt]=i;
        while (x%i==0) x/=i;
    }
    if (x>1)
    {
        p[++cnt]=x;
    }
}
int left(int x)
{
    int sum=0;
    for (int i=1;i<(1<<cnt);i++)
    {
        int tmp=1,one=0;
        for (int j=0;j<cnt;j++)
        {
            if (i&(1<<j))
            {
                one++;
                tmp*=p[j+1];
            }
        }
        if (one&1)
        {
            sum+=x/tmp;
        }
        else sum-=x/tmp;
    }
    return x-sum;
}
int main()
{
    while (~scanf("%d%d",&m,&k))
    {
        getprime(m);
        int l=1,r=inf,mid,ans;
        while (l<=r)
        {
            mid=l+r>>1;
            int pt=left(mid);
            if (pt>=k)
            {
                if (pt==k) ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%d
",ans);
    }
    return 0;
}