\(N, M\) をそれぞれ \(\text{GCD}(N, M)\) で割って、\(N\) と \(M\) は互いに素であるものとします。

「\(N\) と \(M\) のうちちょうど一方で割り切れる数の集合」は \(N \times M\) 周期になっていて、\(1\) 周期に \(N + M - 2\) 個の要素が含まれます。\(S := N + M - 2\) と定義します。

周期的なので、\(S\) で割ったあまりを取って \(1 \le K \le S\) の場合を解けば良いです。これは、\(N\) の倍数の列と \(M\) の倍数の列をマージして \(K\) 番目の要素を得る問題なので、\(O(K)\) 時間で解くことができます。

実装例 (Python)

from math import gcd

N, M, K = map(int, input().split())
# gcd で割る
G = gcd(N, M)
N //= G
M //= G

S = N + M - 2
K -= 1

# S で割る
ans = (K // S) * (N * M)
K %= S

# 答えを求める
n = N
m = M
for _ in range(K):
    if n < m:
        n += N
    else:
        m += M
ans += min(n, m)

# gcd で割ったのを戻す
print(ans * G)