POJ 2773 Happy 2006 二分+容斥原理（二进制枚举或dfs）

算法分析：

题意：

给你m和k，求第k个与m互质的数。

分析：

另一种做法，虽然没这个快，但好理解（点这里）

根据唯一分解定理： 对一个数进行因式分解， 最终必定能分解为多个素数相乘的式子， 且这个式子是唯一的（1除外）。

我们假设1~mid就是满足有k个与m互素的数，然后我们保证mid最小就可以了。

二分的思想，从k到inf进行二分，二分出最小的mid（mid有可能存在12个与m互素的数，但mid与m不互素）符合有k个与m互素的数的数。

对于就1到mid中有多少个与m互素的数需要用到容斥原理：

比如假设m=12；mid=13

12=2*2*3

那么1到mid中与m不互质的数就有2,3,4,6,8,9,10,12，

其实就是2的所有倍数，以及3的所有倍数

这样我们就 算出与1到13中与12不互素的个数为： 13/2+13/3-13/(2*3)=8;

容斥原理：详细解释

第二个公式/

互素的数就位13-8=5；

所以与m不互素的数其实对m进行因式分解，容斥原理。

代码实现：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const ll LNF = 9e18;
ll fac[maxn]; 
ll m,k,sum=0;
void init()           //获取质因子
{
    sum = 0;
    ll tmp = m;
    for(ll i = 2; i*i<=tmp; i++)    //官方版的唯一分解定理
    if(tmp%i==0)
    {
        fac[sum++] = i;
        while(tmp%i==0) tmp /=  i;
    }
    if(tmp>1) fac[sum++] = tmp;
}
ll cal(ll temp)
{
	if(m==1) return temp;
	if(temp==1) return 1;//两个剪枝
	
	ll ret=0;
	//二进制枚举
	 for(int i = 1; i < (1<<sum); i++) //从0～2^n-1个状态,遍历每一个集合
    {
    	
    	ll cnt=0,p=1;
        for(int j = 0; j <sum; j++) //遍历二进制的每一位
        {
            if(i & (1 << j))//判断二进制第j位是否存在
            {
            	p*=fac[j];
                cnt++;
            }
        }
        if(cnt&1)      //cnt为奇数   ,容斥原理
		{
			ret+=temp/p;
		}
		else
		{
			ret-=temp/p;
		}
    }
    
    return temp-ret;

}
int two()
{
	
	ll l=k,r=LNF,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(cal(mid)>=k)
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	printf("%lld\n",l);    
}
int main()
{
     while(scanf("%lld%lld",&m,&k)!=EOF)
	 {
	 	 init();
	 	 two();
	 }
    return 0;
}

dfs

ll n, k;
ll factor[MAXN], sz;
ll sum, mid;
 
void prime_factor(ll n) {
    sz = 0;
    for (ll i = 2; i*i <= n; i++) if (n%i == 0) {
        factor[sz++] = i;
        while (n%i == 0) n /= i;
    }
    if (n > 1) factor[sz++] = n;
}
 
void dfs(ll id, ll step, ll num) {
    if (id == sz) {
        if (step != 0) {
            if (step & 1) sum += mid / num;
            else sum -= mid / num;
        }
        return;
    }
    dfs(id + 1, step, num);
    if (num*factor[id] <= mid)
        dfs(id + 1, step + 1, num*factor[id]);
}
 
int main() {
    while (cin >> n >> k) {
        prime_factor(n);
        ll l = k, r = 1e18, ans = l;
        while (l <= r) {
            mid = (l + r) / 2;
            sum = 0;
            dfs(0, 0, 1);
            if (mid - sum >= k) r = mid - 1, ans = mid;
            else l = mid + 1;
        }
        cout << ans << endl;
    }
    return 0;
}