POJ 2773 Happy 2006（容斥原理+二分）

2006 1
2006 2
2006 3

1
3
5

这道题目是HDU 3388的简化版，方法几乎一模一样

http://blog.csdn.net/dacc123/article/details/51285731

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const LL INF=(LL)1<<62;
#define MAX 1000000
LL prime[MAX+5];
LL sprime[MAX+5];
LL q[MAX+5];
LL check[MAX+5];
LL m,k,cnt;
void eular()
{
    memset(check,false,sizeof(check));
    int tot=0;
    for(int i=2;i<=MAX+5;i++)
    {
        if(!check[i])
            prime[tot++]=i;
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>MAX+5) break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
void Divide(LL n)
{
    cnt=0;
    LL t=(LL)sqrt(1.0*n);
    for(LL i=0;prime[i]<=t;i++)
    {
        if(n%prime[i]==0)
        {
            sprime[cnt++]=prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    }
    if(n>1)
        sprime[cnt++]=n;
}
LL Ex(LL n)
{
    LL sum=0,t=1;
    q[0]=-1;
    for(LL i=0;i<cnt;i++)
    {
         LL x=t;
        for(LL j=0;j<x;j++)
        {
            q[t]=q[j]*sprime[i]*(-1);
            t++;
        }
    }
    for(LL i=1;i<t;i++)
        sum+=n/q[i];
    return sum;
}
LL binary()
{
    LL l=1,r=INF;
    LL mid,ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if((mid-Ex(mid))>=k)
        {
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    eular();
    while(scanf("%lld%lld",&m,&k)!=EOF)
    {
        if(m==1)
        {
            printf("%lld\n",k);
            continue;
        }
        Divide(m);
        printf("%lld\n",binary());
    }
    return 0;
}