Vacib elmi rəqəm#11057

Vacib elmi rəqəm (Həll təhlili)

Bizə məlumdur ki:

$a + x$ a + x $b$ -yə bölünür;
$b + x$ b + x $a$ -ya bölünür;

Nəticədə, $a + b + x$ a + b + x həm $a$ , həm də $b$ -yə bölünür, bu, $a + b + x$ a + b + x-in $N O K (a, b)$ NOK(a, b)-yə bölünməsi ilə ekvivalentdir. Yəni elə bir $k$ rəqəmi mövcuddur ki,

a + b + x = k \cdot N O K (a, b)

a + b + x = k \cdot NOK(a, b)

$x$ kimi $N O K (a, b) - a - b$ NOK(a, b) - a - b götürək. Lakin bu rəqəm mənfi olarsa, onun əvəzinə belə götürək:

x = 2 \cdot N O K (a, b) - a - b

x = 2 \cdot NOK(a, b) - a - b

Görünür, $a + b \leq 2 \cdot N O K (a, b)$ a + b \le 2 \cdot NOK(a, b).

Nümunə

İkinci nümunədə $a = 3, b = 4. N O K (3, 4) = 12$ a = 3, b = 4.~NOK(3, 4) = 12.

Cavab $x = N O K (a, b) - a - b = 12 - 3 - 4 = 5$ x = NOK(a, b) - a - b = 12 - 3 - 4 = 5-ə bərabərdir.

Üçüncü nümunədə $a = 123, b = 123. N O K (123, 123) = 123$ a = 123, b = 123. NOK(123, 123) = 123.

Cavab $x = N O K (a, b) - a - b = 123 - 123 - 123 = - 123$ x = NOK(a, b) - a - b = 123 - 123 - 123 = -123-ə bərabərdir. Bu rəqəm mənfi olduğu üçün cavab belə olacaq:

x = 2 \cdot N O K (a, b) - a - b = 2 \cdot 123 - 123 - 123 = 0

x = 2 \cdot NOK(a, b) - a - b = 2 \cdot 123 - 123 - 123 = 0

Alqoritmın Tətbiqi

gcd funksiyası $a$ və $b$ rəqəmlərinin ən böyük ortaq bölənini hesablayır.

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

Giriş məlumatlarını oxuyuruq.

cin >> a >> b;

$l c m = N O K (a, b) = (a \cdot b) / N O D (a, b)$ lcm = NOK(a, b) = (a \cdot b)~/~NOD(a, b)-ni hesablayırıq.

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

Cavabı hesablayırıq.

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

Cavabı çıxarırıq.

cout << res << endl;