eolymp

Найбільший спільний дільник та найменше спільне кратне

   Кожен з нас вивчав у школі, що таке найбільший спільний дільник (далі НСД) двох чисел a та b. Звичайно, це найбільше ціле число d, на яке a та b діляться без остачі. Не важко обчислити, наприклад, НСД(12, 18) = 6. Але що робити, якщо одне з чисел дорівнює 0? А якщо a чи b від’ємне? Над цим питанням на шкільних уроках, напевне, міркував не кожен учень. Для того щоб коректно відповісти на ці питання, наведемо означення найбільшого спільного дільника.

   Означення 1.Найбільшим спільним дільником (далі НСД) двох цілих чисел a та b, які одночасно не дорівнюють нулю, називається таке найбільше ціле число d, на яке a та b діляться без остачі. Цей факт позначається так: d = НСД(a, b). Якщо обидва числа дорівнюють нулю, то покладемо НСД(0, 0) = 0.

   Виходячи з означення, мають місце наступні співвідношення:

   НОД(a, b) = НОД(b, a),

   НОД(a, b) = НОД(-a, b)

   НОД(a, 0) = |a|

   Чому, наприклад, НСД(-12, 18) дорівнює 6, а не -6? Адже ж числа -12 та 18 діляться націло на 6 та на -6. Відповідь є простою: НСД – це найбільший спільний дільник, а число 6 більше за -6.

   З поняттям найбільшого спільного дільника тісно пов’язане поняття найменшого спільного кратного.

   Означення 2.Найменшим спільним кратним (далі НСК) двох цілих чисел a та b називається найменше додатне ціле число, кратне як a, так і b.

   Основна теорема арифметики стверджує, що довільне натуральне число n можна подати у вигляді добутку простих чисел:

medv_gcd_02

   Такий розклад натурального числа називається канонічним. З нього випливає, що якщо

 medv_gcd_03

то

medv_gcd_04

   Приклад 1. Розглянемо числа a = 24 та b = 18. Розкладемо їх на прості множники: 24 = 23·3, 18 = 2·32. Отже

   НОД(24, 18) = 2min(3,1) · 3min(1,2) = 21 · 31 = 6,

   НОК(24, 18) = 2max(3,1) · 3max(1,2) = 23 · 32 = 8 · 9 = 72

   Як раз такий метод, базований на використанні канонічного розкладу чисел, ми вивчаємо у школі для знаходження НСД та НСК. Але цей метод не є ефективним для реалізації алгоритмів їх обчислення.

   Розглянемо наступний очевидний факт. Якщо НСД(a, b) = d, то a та b діляться на d. Отже їх різниця ab також ділиться на d. Має місце наступне рекурентне співвідношення для обчислення НСД:

medv_gcd_05

   Приклад 2. Нехай a = 32, b = 12. Тоді

   НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =

   = НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4

   Наведений метод обчислення також не є оптимальним. Наприклад, для знаходження НСД(1000000, 2) слід виконати 500000 операцій віднімання. Для прискорення обчислення НСД операцію віднімання замінимо операцією взяття залишку від ділення:

medv_gcd_06

    Приклад 3. Нехай a = 78, b = 14. Тоді

   НОД(78, 14) = НОД(78 mod 14, 14) = НОД(8, 14) = НОД(8, 14 mod 8) = НОД(8, 6) =

   = НОД(8 mod 6, 6) = НОД(2, 6) = НОД(2, 6 mod 2) = НОД(2, 0) = 2

    Спростимо наведену вище рекурентність, скоротивши кількість умов до двох:

medv_gcd_07

   Якщо a < b, то НСД(a, b) = НСД(b, a mod b) = НСД(b, a), тобто аргументи функції НСД переставляються. При наступних викликах функції НСД перший аргумент завжди більший за другий. Нулем може стати лише другий аргумент b.

   Пример 4. Пусть a = 14, b = 78. Тогда

   НОД(14, 78) = НОД(78, 14) = НОД(14, 8) = НОД(8, 6) = НОД(6, 2) = НОД(2, 0) = 2

    Реалізуємо мовою програмування Сі функцію gcd (Greatest Common Divisor) обчислення НСД, використовуючи останню наведену рекурентність. Знак % в Сі позначає операцію обислення остачі при діленні.

int gcd(int a, int b)

{

  if (b == 0) return a;

  return gcd(b, a % b);

}

   Нагадаємо, що умовний оператор в мові Сі має наступний синтаксис::

if (<умовний вираз>) <вираз 1>; else <вираз 2>;

Якщо <умовний вираз> є істинним, то виконується <вираз 1>, інакше виконується <вираз 2>.

   Тернарний умовний оператор має наступний синтаксис:

< умовний вираз > ? < вираз 1 > : < вираз 2 >

та семантично дещо відрізняється від оператора if..then..else. Якщо < умовний вираз > є істинним, то оператор повертає значення, яке повертає < вираз 1 >, інакше повертається значення виразу < вираз 2 >.

   Використовуючи тернарний оператор, функцію gcd можна записати наступним чином:

int gcd(int a, int b)

{

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

}

   Теорема. Між НСД та НСК двох чисел має місце наступне співвідношення:

a · b = НОД(a, b) · НОК(a, b)

   Функція lcm (Lowest Common Multiple) обчислення НСК має вигляд:

int lcm(int a, int b)

{

  return a / gcd(a, b) * b;

}

   Відмітимо, що при обчисленні виразу a * b / gcd(a, b) можливе переповнення, а при обчисленні a / gcd(a, b) * b ні. Вважаємо, що значення a, b та lcm(a, b) знаходяться в межах типу int.

   СПИСОК ЛІТЕРАТУРИ

   1. "Алгоритмы построение и анализ", Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., – Москва, Санкт-Петербург, Киев, 2005 – 1292 с.

   2. [Вальядолид] http://acm.uva.es/problemset.