Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long m, n;
    cin >> m >> n;
    long g = __gcd(m, n);
    m /= g;
    n /= g;
    cout << (n + m - 2) << " ";
    if(n % 2 == 0 and m % 2 != 0) cout << 4;
    if(n % 2 != 0 and m % 2 != 0) cout << 3;
    if(n % 2 != 0 and m % 2 == 0) cout << 2;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long m, n;

cin >> m >> n;

long g = __gcd(m, n);

m /= g;

n /= g;

cout << (n + m - 2) << " ";

if(n % 2 == 0 and m % 2 != 0) cout << 4;

if(n % 2 != 0 and m % 2 != 0) cout << 3;

if(n % 2 != 0 and m % 2 == 0) cout << 2;

return 0;

}

Решение

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