11057. Important
scientific number
Pin was
assembling his new, highly important invention. However, at some point, he
noticed an error in one of the formulas, which might have caused him to
assemble one of the components incorrectly.
After carefully
examining the component and correcting the formula, Pin discovered that it
contained two gears with a and b teeth, respectively. For the
component to function correctly, the gears should have sizes a + x and b
+ x and, where x is a non-negative integer that satisfies the
following conditions:
·
a + x is divisible by b;
·
b + x is divisible by a.
Pin is very
tired and asks for help in finding the smallest suitable value of x.
Since he does not like overly large gears, the smallest possible x
should be chosen among all valid options.
Input. One line contains two
integers a and b (1 ≤ a, b ≤ 109)
– the sizes
of the gears in the component.
Output. Print one non-negative
integer x – the minimum number of teeth needed for the gears to function
correctly.
|
Sample
input 1 |
Sample
output 1 |
|
8 1 |
7 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 4 |
5 |
|
|
|
|
Sample
input 3 |
Sample
output 3 |
|
123 123 |
0 |
GCD, LCM
We
know that:
·
a + x is divisible by b;
·
b + x is divisible by a;
Therefore, a + b + x is divisible by both a and b, which is
equivalent to its divisibility by LCM(a, b). That is,
there exists an integer k such that:
a + b + x = k
* LCM(a, b)
We
take x = LCM(a, b) – a – b
as the solution. However, if this value is negative, we
instead use:
x
= 2 * LCM(a, b) – a – b
It
is evident that a + b ≤
2 * LCM(a, b).
Example
In
the second example a
= 3, b = 4. LCM(3, 4) = 12.
The
answer is x
= LCM(a, b) – a – b = 12 – 3 – 4 = 5.
In
the third example a
= 123, b = 123. LCM(123, 123) = 123.
The
answer is x
= LCM(a, b) – a – b = 123 –
123 – 123
= -123. Since this value is negative, the
answer is
x
= 2 * LCM(a, b) – a – b = 2 * 123 –
123 – 123 = 0
Algorithm implementation
The function gcd computes the greatest common divisor of the
numbers a and b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Read the input data.
cin >> a >> b;
Compute lcm = LCM(a, b) = (a * b) / GCD(a, b).
lcm = a / gcd(a, b) * b;
Compute the answer.
res = lcm - a - b;
if (res
< 0) res += lcm;
Print the answer.
cout << res << endl;