11057. Важное научное число
Пин собирал своё
новое, крайне важное изобретение. Однако в какой-то момент он заметил ошибку в
одной из формул, из-за чего мог неправильно собрать одну из деталей.
Внимательно
изучив деталь и исправив формулу, Пин обнаружил, что в ней установлены две
шестерёнки с a и b зубцами соответственно. Чтобы деталь работала
правильно, шестерёнки должны иметь размеры a + x и b
+ x, где x – неотрицательное целое число, удовлетворяющее следующим
условиям:
·
a + x делится на b;
·
b + x делится на a.
Пин очень устал
и просит помочь ему найти наименьшее подходящее значение x. Поскольку он
не любит слишком большие шестерёнки, из всех возможных вариантов следует
выбрать минимальное.
Вход. В одной строке
заданы два целых числа a и b (1 ≤ a, b ≤
109) – размеры шестерёнок в детали.
Выход. Выведите одно
целое неотрицательное число x – минимальное количество зубцов, которых
не хватает шестерёнкам, чтобы изобретение работало правильно.
|
Пример
входа 1 |
Пример
выхода 1 |
|
8 1 |
7 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 4 |
5 |
|
|
|
|
Пример
входа 3 |
Пример
выхода 3 |
|
123 123 |
0 |
НОД,
НОК
Нам известно что:
·
a + x делится на b;
·
b + x делится на a;
Следовательно, a + b + x делится и на a, и на b, что эквивалентно делимости a + b + x на НОК(a, b). То
есть существует такое число k, что
a + b + x = k
* НОК(a, b)
В качесстве x возьмем НОК(a, b) – a – b. Однако если это число отрицательное, то вместо него возьмем
x
= 2 * НОК(a, b) – a – b
Очевидно, что a + b ≤ 2 * НОК(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. Так как это число отрицательное, то ответом будет
x
= 2 * НОК(a, b) – a – b = 2 * 123 –
123 – 123 = 0
Реализация алгоритма
Функция 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 * b) / НОД(a, b).
lcm = a / gcd(a, b) * b;
Вычисляем ответ.
res = lcm - a - b;
if (res
< 0) res += lcm;
Выводим ответ.
cout << res << endl;