描述两个数的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进行质因数分解，求出m有哪些质因数，然后用容斥求[1, mid]内与m互质的数有多少个。
判断的时候，[1,mid]之间与m互质的数的数量 = mid - （包含一个质因子的数的个数）+ （包含2个质因子的书的个数）-（包含3个质因子的数的个数）+ （包含4个质因数的数的个数）……
#include <cstdio>
// 对n进行素因子分解， fac[0]记录因子个数；
int fac[20];
void Div(int n) {
int k = 0;
for(int i = 2; i * i <= n; ++i){
if(n % i == 0) fac[++k] = i;
while(n % i == 0) n /= i;
}
if(n > 1) fac[++k] = n;
fac[0] = k;
}
// 计算[1, n]内与m互质的数的个数
int que[1<<10];
int Count(int n, int m) {
int g = 0, sum = n;
que[++g] = 1;
for(int i = 1; i <= fac[0]; ++i){
int t = g;
for(int j = 1; j <= g; ++j){
que[++t] = que[j] * fac[i] * -1;
sum += n / que[t];
}
g = t;
}
return sum;
}
// 二分，二分枚举一个答案mid，计算[1, mid]内有多少个数与m互质，让答案与K比较；
int Binary_search(int m, int K){
int l = 1, r = 2000000000, mid;
while(l <= r){
mid = (l + r) >> 1;
if(Count(mid, m) >= K) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main()
{
int m, K;
while(scanf("%d%d", &m, &K) != EOF)
{
Div(m);
int ans = Binary_search(m, K);
printf("%d\n", ans);
}
return 0;
}