ABC341D

2024-02-19

题解

先想一个问题：哪些数满足恰好只被 $N$ 和 $M$ 中一个数整除？

很简单，是 $N$ 的倍数加上 $M$ 的倍数，再除去 $N$ 和 $M$ 的最小公倍数的倍数。

我们令 $N$ 和 $M$ 的最小公倍数为 $l c m$ 。那么 满足条件的这些数是以 $l c m$ 为循环节出现的。 证明很简单：如果在 $1 \sim l c m$ 这些数中， $a_{1}, a_{2}, \dots, a_{n}$ 符合要求，那么 $a_{i} + k \times l c m$ 也一定符合要求。

我们设 $1 \sim l c m$ 中符合条件的数有 $s$ 个。那么每个 $k \times l c m + 1 \sim (k + 1) \times l c m$ 中符合条件的数就有 $s$ 个。我们要找第 $K$ 小的数，就要先锁定 $k$ 。

$k = \frac{(K - 1)}{s}$ ，小学生数学题。这时就是要找 $k \times l c m + 1 \sim (k + 1) \times l c m$ 中第 $((K - 1) mod s) + 1$ 个满足条件的数了。我们先把 $k \times l c m$ 放进优先队列里，然后执行 $((K - 1) mod s) + 1$ 次如下操作：

取出队首 $x$ 。如果 $x$ 是 $N$ 的倍数，把 $x + N$ 放进优先队列；如果 $x$ 是 $M$ 的倍数，把 $x + M$ 放进优先队列。

队首即为答案。

不懂可以配合代码食用：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, K, ans;
priority_queue<int, vector<int>, greater<int> > q;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m >> K;
	int lcm = n * m / __gcd(n, m);
	int s = (lcm / n - 1) + (lcm / m - 1);
	int k = (K-1) / s;
	K = (K-1) % s + 1;
    q.push(k * lcm);
	while (K--) {
		int x = q.top(); q.pop();
		if (x % n == 0) q.push(x+n);
		if (x % m == 0) q.push(x+m);
	}
	cout << q.top();
	return 0;
}