利用与 n 互质的数按长度 n 周期重复、每段恰有 phi(n) 个的性质，先定位块号，再在 1..n 中找对应位置。
OJ: luogu
题目 ID: P1592
难度:普及+/提高
标签:数论最大公约数思维
日期: 2026-06-20 11:48
题意
给定两个正整数 n,k，要求输出按从小到大排列时，第 k 个与 n 互质的正整数。
思路
先看一个最直接的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long gcd_value(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
// brute.cpp：直接从 1 开始枚举正整数，
// 找到第 k 个与 n 互质的数。
// 复杂度与答案大小成正比，只适合小数据对拍。
long long cnt = 0;
for (long long x = 1; ; x++) {
if (gcd_value(x, n) == 1) {
cnt++;
if (cnt == k) {
cout << x << '\n';
return 0;
}
}
}
return 0;
}brute.cpp 从 1 开始一个一个枚举正整数，只要和 n 的最大公约数是 1，就把它计入答案。
这个做法完全正确，但如果第 k 个数本身很大，就会枚举很多整数，不适合大数据。
关键观察：按 n 为长度，分布会周期重复
对于任意整数 x：
gcd(x, n) = gcd(x + n, n)
因为 x+n 和 x 对 n 取模后的余数相同。
这说明：
- 在区间
1..n中哪些数和n互质 - 和在区间
n+1..2n中哪些数和n互质 - 以及后面每一段长度为
n的区间
它们的相对位置完全一样。
每一段里有多少个？
长度为 n 的一整段里，与 n 互质的数恰好有：
phi(n)
个，这里 phi(n) 就是欧拉函数。
所以我们可以把答案按整段切开：
- 前面有多少整段已经完整跳过
- 当前这一段里，要找第几个与
n互质的数
设：
block_cnt = (k - 1) / phi(n)need = (k - 1) % phi(n) + 1
那么答案一定是：
- 前面先跳过
block_cnt段，每段长度都是n - 再在
1..n中找到第need个与n互质的数
最后答案就是：
block_cnt * n + pos
其中 pos 表示 1..n 中第 need 个与 n 互质的位置。
实现细节
先用试除法计算 phi(n)。
然后扫描 1..n，统计有多少个数与 n 互质。
当数到第 need 个时，就可以直接得到最终答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long gcd_value(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
// 用试除法计算单个 n 的欧拉函数 phi(n)。
long long euler_phi(long long x) {
long long ans = x;
for (long long p = 2; p * p <= x; p++) {
if (x % p != 0) {
continue;
}
ans = ans / p * (p - 1);
while (x % p == 0) {
x /= p;
}
}
if (x > 1) {
ans = ans / x * (x - 1);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
long long phi_n = euler_phi(n);
// 每一段长度为 n 的区间里，与 n 互质的数的分布完全重复，
// 并且每段恰好有 phi(n) 个。
long long block_cnt = (k - 1) / phi_n;
long long need = (k - 1) % phi_n + 1;
long long cnt = 0;
for (long long i = 1; i <= n; i++) {
if (gcd_value(i, n) == 1) {
cnt++;
if (cnt == need) {
cout << block_cnt * n + i << '\n';
return 0;
}
}
}
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的核心不是一直往后枚举，而是发现“与 n 互质”的分布会按长度 n 周期重复。
再结合每段恰好有 phi(n) 个合法数，就能把“第 k 个”转成：
- 先算它落在哪一段
- 再算它在这一段里的第几个位置
这样复杂度就降下来了。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
