| Автор: | А. Кленин, М.Спорышев | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Однажды у студента Васи спросили, сколько студентов обучается в его университете. Вася забыл это число, однако вспомнил, что недавно на сайте университета была опубликована интересная статистика: ровно P процентов от общего числа студентов обучаются на программиста, и ровно S процентов студентов, обучающихся на программиста, получают стипендию.
Помогите Васе узнать минимально возможное общее число студентов в его университете.
Входной файл содержит целые числа P S.
Выходной файл должен содержать единственное целое число — минимально возможное количество студентов.
1 ≤ P, S ≤ 100
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
Обозначим за x количество студентов в университете. Заметим, что x является допустимым количеством студентов тогда и только тогда, когда P процентов от x и S процентов от P процентов от x являются целыми числами. Кроме того, x должно быть целым положительным числом.
Таким образом, необходимо найти наименьшее натуральное x, такое что xP кратно 100, а xPS кратно 10000. Отсюда следует, что x = min(100gcd(P, 100), 10000gcd(PS, 10000)). Здесь gcd — наибольший общий делитель двух чисел, который может быть найден, например, с помощью алгоритма Евклида.
Допускается также решение, перебирающее все натуральные числа, и выбирающее первое, удовлетворяющее условию задачи.