1151. Кладоискатель

Юный искатель сокровищ Рома прошёл курс по “кладоискательству” и теперь отправился на летнюю практику. Практика проходит неподалёку от деревни “Каменные зори” и длится ровно b дней. Каждый день Рома находит a монет, зарытых в земле. Таким образом, к концу первого дня у него будет a монет, к концу второго – 2 * a, а к завершению практики Рома накопит b * a монет.

Если в конце дня ответственный преподаватель замечает, что количество монет у Ромы делится на b, Рома может взять пирожок с полки и тут же съесть его. Помогите Роме определить, сколько пирожков он съест за всё время практики.

Вход. Два целых числа a и b (1 ≤ a, b ≤ 10⁹).

Выход. Выведите количество пирожков, которые Рома съест за время практики.

Пример входа	Пример выхода
2 1	1

РЕШЕНИЕ

НОД

Анализ алгоритма

Количество пирожков, съеденных Ромой, равно НОД(a, b).

Реализация алгоритма

Фукция gcd вычисляет наибольший общий делитель чисел a и b.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Читаем входные данные.

scanf("%d %d", &a, &b);

Вычисляем и выводим ответ.

d = gcd(a, b);

printf("%d\n", d);