只被其中一个整除

题目描述

给你三个正整数 $N$、$M$ 和 $K$。其中 $N$ 和 $M$ 不同。

输出第 $K$ 小的、恰好被 $N$ 和 $M$ 中的一个整除的正整数。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$

输出格式

输出第 $K$ 小的、恰好被 $N$ 和 $M$ 中的一个整除的正整数。

样例

2 3 5

9

恰好被 $2$ 和 $3$ 中的一个整除的正整数按升序为 $2, 3, 4, 8, 9, 10, \ldots$。

注意 $6$ 能被 $2$ 和 $3$ 同时整除，所以不包含在内。

满足条件的第 5 小的正整数是 $9$，因此输出 $9$。

1 2 3

5

满足条件的数按升序为 $1, 3, 5, 7, \ldots$。

100000000 99999999 10000000000

500000002500000000

数据范围

• $1 \le N, M \le 10^8$
• $1 \le K \le 10^{10}$
• $N \neq M$
• $N$、$M$、$K$ 均为整数