Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Квадраты

НОД и алгоритм Евклида

Квадраты

Ограничения: время – 1s/Java 2s, память – 8MiB

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, 1 ≤ A, B ≤ 231 − 1). Мальчик Сеня очень любит резать прямоугольники с особым цинизмом, и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты. Сколько же он нарежет квадратов?
Ввод
Числа A и B.
Вывод
Количество получившихся квадратов.

Пример ввода

1 2

Пример вывода

2
Источник: Турнир "Экспонента-2006"


Единичный НОД

НОД и алгоритм Евклида

Заданы два натуральных числа в десятичной системе счисления, состоящие из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти НОД этих чисел.
 
Напомним, что НОД (наибольший общий делитель) двух чисел a и b — это такое максимальное число c, что b делится на c и a делится на c.
 
Входные данные
В единственной строке  записаны два целых числа N и M (1 ≤ N, M ≤ 2000).
 
Выходные данные
Выведите ответ без ведущих нулей.

Ввод Вывод
1 1 1
1 2 1

Апельсины

НОД и алгоритм Евклида

Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов.
 
Она хочет разрезать каждый апельсин на одинаковое число равных долек так, чтобы их можно было распределить между гостями (сама Катя апельсины есть не будет), и всем гостям досталось поровну долек.
 
Напишите программу, которая вычисляет минимальное количество долек, на которое необходимо разрезать каждый апельсин, чтобы были выполнены указанные выше условия.

Входные данные
Входная строка содержит два положительных целых числа n и m (1 ≤ n, m ≤ 109).
 
Выходные данные
Выведите ответ на задачу.

Ввод Вывод
2 5 2
2 4 1