http://poj.org/problem?id=2773
说实话这道题。。一点都不Happy好吗
似乎还可以用欧拉函数来解这道题，但正好刚学了容斥原理和二分，就用这个解法吧。
题解：要求输出[1,m]中与m互质的第k个数，先打表，找到m的所有质因数，然后用二分实现，最开始区间为[1,2^60]，利用容斥原理去找区间[1,mid]内素数的个数t，不断进行二分，直到所查找的区间[l,r]内素数的个数t等于k，mid=l=r，则此时的l就是第k个与m互质的数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define N 1000005 vector<int> v;
void getPrime(int n) //[l,r]内与n互素的数字个数
{
v.clear();
//筛选素数
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
v.push_back(i);
while(n%i==0)
n/=i;
}
}
if(n>1)
v.push_back(n);
} ll solve(ll n)
{
//容斥原理的二进制解法
int len=v.size();
ll res=0;
for(int i=1;i<(1<<len);i++)
{
int cnt=0;
ll val=1;
for(int j=0;j<len;j++)
{
if(i&(1<<j))
{
cnt++;
val*=v[j];
}
}
if(cnt&1) //若为奇数项进行加法，偶数项进行减法
res+=n/val;
else res-=n/val;
}
return n-res;
} int main()
{
int m,K;
while(~scanf("%d%d",&m,&K))
{
getPrime(m);
ll l=1,r=(1ll<<60),mid,t;
while(l<r)
{
mid=((l+r)>>1);
t=solve(mid);
if(t>=K)
r=mid;
else l=mid+1;
}
printf("%I64d\n",l);
}
return 0;
}