#ABC341D. 两个中只有一个

两个中只有一个

问题描述

给你三个正整数 NNMMKK。这里,NNMM 是不同的。打印正好可被 NNMM 中的一个(不得同时)整除的第 KK 小正整数。

数据规模

1N,M1081\leq N,M\leq 10^8

1K10101\leq K\leq 10^{10}

NMN\neq M

N,MN,MKK 是整数。

输入

输入来自标准输入,格式如下:

N M KN\ M\ K

输出

打印可被 NNMM 中的一个整除的第 KK 个最小正整数。

2 3 5
9

能被 23 中的一个整除的正整数是 2348910。请注意,不包括 6,因为它可以被 23 整除。满足条件的第五个最小正整数是 9,所以我们打印 9

1 2 3
5

满足条件的数字按升序排列为 1357

100000000 99999999 10000000000
500000002500000000