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

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

我们令 $N$ 和 $M$ 的最小公倍数为 $lcm$。那么 满足条件的这些数是以 $lcm$ 为循环节出现的。 证明很简单：如果在 $1 \sim lcm$ 这些数中，$a_1,a_2,\cdots,a_n$ 符合要求，那么 $a_i+k \times lcm$ 也一定符合要求。

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

$k = \frac{(K-1)}{s}$，小学生数学题。这时就是要找 $k\times lcm+1 \sim (k+1) \times lcm$ 中第 $((K-1) \bmod s)+1$ 个满足条件的数了。我们先把 $k \times lcm$ 放进优先队列里，然后执行 $((K-1) \bmod 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;
}