e-olymp 58. Биллиард

Задача

Биллиард представляет собой прямоугольник размерами [latex] M \times N [/latex], где [latex] M [/latex] и [latex] N [/latex] — натуральные числа. Из верхней левой лузы вылетает шар под углом [latex] 45^{\circ} [/latex] к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

Входные данные

Во входной строке два числа [latex] M [/latex] и [latex] N [/latex], [latex] 1 ≤ M, N ≤ 2000000000 [/latex]. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. [latex] M [/latex] — горизонтальная сторона биллиарда, [latex] N [/latex] — вертикальная сторона биллиарда.

Выходные данные

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные Выходные данные
2 1 1 2
5 6 9 4
12 33 13 2
156 156 0 3
654 236 443 4

Код программы

Решение

Чтобы решить эту задачу, необходимо найти НОД значений [latex] M [/latex] и [latex] N [/latex] из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во 2 строке. Далее, в 8 строке, введем перемененную [latex] g [/latex] и присвоим ей значение НОД для [latex] M [/latex] и [latex] N [/latex]. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Добавить комментарий