Важливе наукове число (Розбір)

Нам відомо, що:

• a + x ділиться на $b$;

• b + x ділиться на $a$;

Отже, a + b + x ділиться і на $a$, і на $b$, що еквівалентно діленню a + b + x на НСК(a, b). Тобто існує таке число $k$, що

Як $x$ візьмемо НСК(a, b) - a - b. Однак, якщо це число від'ємне, то замість нього візьмемо

Очевидно, що a + b \le 2 \cdot НСК(a, b).

Приклад

У другому прикладі a = 3, b = 4.~НСК(3, 4) = 12.

Відповідь дорівнює x = НСК(a, b) - a - b = 12 - 3 - 4 = 5.

У третьому прикладі a = 123, b = 123. НСК(123, 123) = 123.

Відповідь дорівнює x = НСК(a, b) - a - b = 123 - 123 - 123 = -123. Оскільки це число від'ємне, то відповіддю буде

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

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

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

Читаємо вхідні дані.

cin >> a >> b;

Обчислюємо lcm = НСК(a, b) = (a \cdot b)~/~НСД(a, b).

lcm = a / gcd(a, b) * b;

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

res = lcm - a - b;
if (res < 0) res += lcm;

Виводимо відповідь.

cout << res << endl;