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.