NYOJ762+POJ1796 第k个互质数(容斥原理+二分)

本文主要是介绍NYOJ762+POJ1796 第k个互质数(容斥原理+二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

两个数的a，b的gcd为1，即a，b互质，现在给你一个数m，你知道与它互质的第k个数是多少吗？与m互质的数按照升序排列。

输入

输入m ，k （1<=m<=1000000;1<=k<=100000000）

输出

输出第k个数。

样例输入

10 1
10 2
10 3

样例输出

1
3
7

思路

题意要求出与m互质的第k个数，首先肯定不能暴力，要用容斥原理解决，在做这个题之前请先做一下:HDU4135 Co-prime(容斥原理)

首先我们可以利用容斥原理知道:1~m(m为任意值)中与n互质的数的个数

然后考虑利用二分查找数字，然后判断这个数字和n有多少个互质数

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
int a[50],b[1010];//a保存n的质因子,a[0]表示质因子个数
void div(int n)//分解质因数
{int j=0;for(int i=2; i*i<=n; i++)if(n%i==0){while(n%i==0)n/=i;a[++j]=i;}if(n>1) a[++j]=n;a[0]=j;
}int get_cnt(int n)//容斥原理来判断二分的mid有多少个与n互质的数
{int g=0,sum=n,t;b[++g]=1;for(int i=1; i<=a[0]; i++){t=g;for(int j=1; j<=g; j++){b[++t]=b[j]*a[i]*-1;sum+=n/b[t];}g=t;}return sum;
}int erfen(int n,int k)
{int mid,l=1,r=(int)2e9;while(l<=r){mid=(l+r)>>1;if(get_cnt(mid)<k)l=mid+1;elser=mid-1;}return l;
}int main()
{int n,k;while(~scanf("%d%d",&n,&k)){div(n);printf("%d\n",erfen(n,k));}return 0;
}