Задача A. Сколько студентов?

Автор:А. Кленин, М.Спорышев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Однажды у студента Васи спросили, сколько студентов обучается в его университете. Вася забыл это число, однако вспомнил, что недавно на сайте университета была опубликована интересная статистика: ровно P процентов от общего числа студентов обучаются на программиста, и ровно S процентов студентов, обучающихся на программиста, получают стипендию.

Помогите Васе узнать минимально возможное общее число студентов в его университете.

Формат входного файла

Входной файл содержит целые числа P S.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимально возможное количество студентов.

Ограничения

1 ≤ P, S ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 20
50
2
2 19
5000

Разбор

Обозначим за x количество студентов в университете. Заметим, что x является допустимым количеством студентов тогда и только тогда, когда P процентов от x и S процентов от P процентов от x являются целыми числами. Кроме того, x должно быть целым положительным числом.

Таким образом, необходимо найти наименьшее натуральное x, такое что xP кратно 100, а xPS кратно 10000. Отсюда следует, что x = min(100gcd(P, 100), 10000gcd(PS, 10000)). Здесь gcd — наибольший общий делитель двух чисел, который может быть найден, например, с помощью алгоритма Евклида.

Допускается также решение, перебирающее все натуральные числа, и выбирающее первое, удовлетворяющее условию задачи.


0.088s 0.011s 13