poj 2773 Happy2006【容斥原理】

Description

Input

Output

Sample Input

2006 1
2006 2
2006 3

Sample Output

1
3
5

题目翻译：给出m,k，求第k个和m互质的数字！

解题思路：数据量较大，因此全部采用long long，想求出第k个互质的数，数据量太大，因此采用2分查找，来找d第K个数字，想知道当前数字t是第几个与m的互质的数，需要求出t前有几个与m不互质的数字，利用容斥原理，可以解决，然后对比即可！

#include<cstdio>
#define LL long long
LL p[20],top;
void getp(LL m){
    LL i;
    for(i=2,top=0;i*i<=m;i++)
        if(m%i==0){
            p[top++]=i;
            while(m%i==0) m/=i;
        }
    if(m>1) p[top++]=m;
}
LL nop(LL mid,LL t){
    LL i,sum=0;
    for(i=t;i<top;i++)
        sum+=mid/p[i]-nop(mid/p[i],i+1);
    return sum;
}
int main(){
    LL k,m;
    while(scanf("%lld%lld",&m,&k)==2){
        LL mid,l=0,r=0x3f3f3f3f3f3f3f3f,t,ans=0;
        getp(m);
        while(l<=r){
            mid=(l+r)>>1;
            t=mid-nop(mid,0);
            if(t>=k){
                r=mid-1;
                if(t==k) ans=mid;
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}