- 描述
- 两个数的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
首先，根据欧几里得可知，gcd(b * t + a, b) = gcd(a, b)(t为任意整数），则如果a与b互质，则b * t + a与b也一定互质，如果a与b不互质，则b*t+a与b也一定不互质，所以与m互质的数对m取模具有周期性。可以先求出1~m之间有多少个数与m互质，然后根据周期性去求第k个与m互质的数。
#include <cstdio> const int N = 1000005; int a[N]; int gcd(int a, int b) { while(b) { int r = a % b; a = b; b = r; } return a; } int main() { int m, k; while(~scanf("%d%d", &m, &k)) { if(m == 1) { printf("%d\n", k); continue; } int num = 0; for(int i = 1; i < m; i++) if(gcd(m, i) == 1) a[num++] = i; int p = k / num; if(k % num == 0) p--; k %= num; if(k == 0) k = num; printf("%d\n", p * m + a[k-1]); } return 0; }用上面的方法可以在POJ上AC，可惜的是，在NYOJ上TLE了。所以要寻找一个更快的解决方案，也就是下面的二分+容斥。
首先对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; }