周期闹钟

题目描述

小 C 设置了两个周期闹钟。第一个闹钟每隔 $a$ 个时间单位响一次，第二个闹钟每隔 $b$ 个时间单位响一次。

计时从时刻 $0$ 开始，但时刻 $0$ 不算作响铃事件。因此，第一个闹钟会在 $a,2a,3a,\ldots$ 时刻响，第二个闹钟会在 $b,2b,3b,\ldots$ 时刻响。

只要至少有一个闹钟响，就记作一次响铃事件。如果两个闹钟在同一时刻同时响，也只记作一次事件。

请你求出第 $k$ 次响铃事件发生的时刻。

输入格式

一行三个正整数 $a,b,k$，分别表示两个闹钟的周期和需要查询的事件编号。

输出格式

输出一个整数，表示第 $k$ 次响铃事件发生的时刻。

样例 1

输入

2 3 5

输出

8

说明

前五次响铃事件依次发生在时刻 $2,3,4,6,8$。时刻 $6$ 两个闹钟同时响，但只记作一次事件。

样例 2

输入

4 6 6

输出

18

说明

前六次响铃事件依次发生在时刻 $4,6,8,12,16,18$。

更多样例

样例 3、样例 4 和样例 5 请分别查看附件中的 Data/sample3.in、Data/sample3.ans，Data/sample4.in、Data/sample4.ans，以及 Data/sample5.in、Data/sample5.ans。

【数据规模与约定】

对于所有测试数据，$1\le a,b,k\le 10^9$，且答案不超过 $10^{18}$。

点击下载本题选手目录