$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)

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)