1. Идея

Нужно сократить отношение a / b до несократимого вида.

Если у чисел a и b есть общий делитель g, то можно разделить и числитель, и знаменатель на g, не меняя само отношение. Чтобы получить минимальные целые части, надо разделить на наибольший общий делитель чисел |a| и b.

Тогда ответ будет таким:

• p = a / g
• q = b / g

где g = gcd(|a|, b).

2. Наблюдения

Наблюдение 1. Отношение не меняется при делении на общий делитель

Если разделить a и b на одно и то же ненулевое число, значение дроби не изменится. Поэтому сокращение дроби — это просто деление обеих частей на их общий делитель.

Наблюдение 2. Нужен именно наибольший общий делитель

Если разделить только на какой-то общий делитель, дробь может остаться сократимой.
Чтобы получить окончательный ответ, нужно делить на gcd(|a|, b).

Наблюдение 3. Почему берётся |a|

В условии требуется, чтобы gcd(|p|, q) = 1.
НОД обычно рассматривают для неотрицательных чисел, поэтому удобно взять |a| и b.

Например:

• a = -6, b = 8
• gcd(|a|, b) = gcd(6, 8) = 2
• после сокращения получим -3 / 4

Наблюдение 4. Случай a = 0

Если a = 0, то отношение равно 0 / b, то есть просто ноль.
Тогда gcd(|a|, b) = gcd(0, b) = b, и получаем:

• p = 0 / b = 0
• q = b / b = 1

Это и есть правильный несократимый вид: 0 1.

3. Алгоритм

1. Считать a и b.
2. Вычислить g = gcd(|a|, b) с помощью алгоритма Евклида.
3. Найти:
   • p = a / g
   • q = b / g
4. Вывести p и q.

4. Почему это работает

Пусть g = gcd(|a|, b).

Тогда:

• g делит |a|, а значит и a,
• g делит b.

Следовательно, числа p = a / g и q = b / g — целые.

Также отношение сохраняется:

• p / q = (a / g) / (b / g) = a / b.

Теперь покажем, что дробь несократима.

Если бы у |p| и q был общий делитель больше 1, то существовало бы число d > 1, которое делит и |p|, и q. Тогда число d * g делило бы и |a|, и b, что противоречит тому, что g — наибольший общий делитель.

Значит, gcd(|p|, q) = 1.

Кроме того, b > 0 по условию, а g > 0, значит q = b / g > 0.

Все требования задачи выполнены.

5. Сложность

Алгоритм Евклида работает за O(log(min(|a|, b))).

Итоговая сложность:

• по времени: O(log(min(|a|, b)))
• по памяти: O(1)

6. Код на C++17

#include <iostream>
using namespace std;

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long aa = a >= 0 ? a : -a;
    long long g = gcd_ll(aa, b);

    long long p = a / g;
    long long q = b / g;

    cout << p << " " << q << "\n";
    return 0;
}

7. Код на Python 3

a, b = map(int, input().split())

x = abs(a)
y = b
while y != 0:
    x, y = y, x % y

g = x
p = a // g
q = b // g

print(p, q)