Максимізуй це! (Розбір)

Розглянемо, які значення приймає вираз f(i, j) = i / n - j / m, де i, j \in Z при фіксованих $n$ та $m$. Наприклад, f(n, m) = n / n - m / m = 0.

Розглянемо, наприклад, функцію f(i, j) = i / 3 - j / 5. Тоді

Згідно з розширеним алгоритмом Евкліда, завжди існують такі цілі $i$ та $j$, що i / 3 - j / 5 = 1. Отже, найменшим додатним значенням, яке може приймати вираз i / 3 - j / 5, є $1/15$. Звідси випливає, що цей вираз може приймати всі можливі значення виду $k/15$, де k \in Z.

Теорема. Якщо f(i, j) = i / n - j / m, то ця функція приймає значення виду k / НСК(n, m), де k \in Z.

Доказ. Дійсно,

Оскільки числа m / НОД(n, m) та n / НОД(n, m) є взаємно простими, то завжди існують такі $i$ та $j$, що чисельник дробу дорівнює $1$. Отже, функція f(i, j) може приймати всі можливі значення виду k / НСК(n, m), де k \in Z.

Тепер розглянемо початкову функцію

Її значення — це відстані від точки $t$ до найближчої точки виду k / НСК(n, m), k \in Z. Для максимізації функції $f(t)$ значення $t$ слід обрати таким чином, щоб воно знаходилося точно посередині між сусідніми точками k / НСК(n, m) та (k + 1) / НСК(n, m), де $k$ — ціле число. Значення функції в такій точці дорівнює 1 / 2 \cdot НСК(n, m), що і буде відповіддю.

Приклад

Нехай f(t) = min_{i,j \in Z} |{i \over 3} - {j \over 5} + t|. Очевидно, що f(0) = 0. Рівність f(1 / 15) = 0 справедлива, оскільки існують такі $i$ та $j$, що i / 3 - j / 5 = -1 / 15 (наприклад, i = 1, j = 2). З цього також випливає, що f(k / 15) = 0, де k \in Z.

Однак f(k / 15 + 1 / 30) = 1 / 30, і це буде найбільшим значенням функції, адже точка k / 15 + 1 / 30 знаходиться на максимальній відстані від нулів функції.

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

Функція gcd обчислює найбільший спільний дільник чисел $a$ та $b$.

long long gcd(long long a, long long b)
{
  return b == 0 ? a : gcd(b, a % b);
}

Функція lcm обчислює найменше спільне кратне чисел $a$ та $b$.

long long lcm(long long a, long long b)
{
  return a / gcd(a, b) * b;
}

Основна частина програми. Зчитуємо вхідні дані.

while (scanf("%lld %lld", &n, &m) == 2)
{

Обчислюємо і виводимо відповідь.

  d = 2 * lcm(n, m);
  printf("%lld/%lld\n", 1, d);
}