|
Темы:
НОД и алгоритм Евклида
Алгоритмы
Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?
Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 109 ).
Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 1 10 |
0 |
| 2 |
1 2 5 |
3 |
|