Най-голям общ делител и най-малко общо кратно

Greatest Common Divisor and Least Common Multiple

Какво е най-голям общ делител?
Какво е най-малко общо кратно?
Разширен алгоритъм на Евклид и приложения

Автор: Соня Милева, Александър Георгиев

Математиката е неизменна част от информатиката независимо дали някои го отричат или не! Следователно логично е да се решават математически задачи в програмирането, което се случва много често по състезания. Най-много такива задачи могат да се срещнат в TopCoder и на руски състезания. Математическите задачи често включват намиране на НОД и НОК (за опростяване на дроби или в задачи свързани с теория на числата) – понякога това директно ни дава отговора, а друг път е само малка, но важна част от голяма заплетена задача.

Най-голям общ делител

?	Ще отбелязваме най-големия общ делител на `A` и `B` като `НОД(A, B)` или `GCD(A, B)`.

Най-голям общ делител (Greatest Common Divisor) на две числа A и B е най-голямото цяло число D, което дели двете числа без остатък. За всеки две цели числа D е поне 1 (тъй като 1 дели всеки две числа).

Дадени са две числа A и B. Да се намери най-големият им общ делител.

Наивният метод е да пробваме всеки един делител на едното число дали дели и другото. Този алгоритъм ще има сложност O(min(A, B)).

int
 gcdNaive(int
 A,
 int B) {
    for
 (int
 i =
 min(A,
 B);
 i >
=
 1
;
 i-
-) {
        if
 (A %
 i =
=
 0
 &
&
 B %
 i =
=
 0) {
            return
 i;
        }
    }
}

Ако сме малко по-умни и първо намерим делителите на едното число, след което проверим кой е максималният от тях, който дели другото, бихме получили сложност O(sqrt(min(A, B))).

Алгоритъм на Евклид (с изваждане)

Алгоритъмът на Евклид за пресмятане на НОД произлиза от теоремата на Безу: ако имаме две неотрицателни цели числа A и B, които имат НОД D, то съществуват цели числа X и Y за които е изпълнено уравнението: A * X + B * Y = D. Следователно НОД на две числа не се променя ако заместим по-голямото с разликата между него и по-малкото. Ако повторим тази процедура докато едното число не стане нула, то в този момент другото число е равно на НОД на двете първоначални. Алтернативно можем да спрем още на стъпката в която двете числа са равни - тогава те са равни и на НОД-а си.

Например за числата 84 и 18 имаме: НОД(84, 18) = НОД(84-18, 18) = НОД(66, 18) = НОД(48, 18) = НОД(30, 18) = НОД(12, 18) = НОД(6, 12) = НОД(6, 6) = 6. Този алгоритъм ще има сложност O(max(A, B)), която се достига при НОД(A, 1) или НОД(1, B).

int
 gcdEuclidSubtraction(int
 A,
 int B) {
    while
 (A !
= B) {
        if
 (A < B) {
            swap(A,
 B);
        }
        A -
=
 B;
    }
    return
 A;
}

Алгоритъм на Евклид (с остатъци)

Предишният алгоритъм може да бъде оптимизиран още, тъй като при голяма разлика между двете числа ще трябва да се направят много изваждания. Можем вместо да заместваме по-голямото число с разликата, да го заместваме с остатъка при делението на по-голямото на по-малкото. При тази оптимизация е доказано, че никога не се правят повече от 5 * (броя цифри на по-малкото число) стъпки. Този алгоритъм ще има сложност O(log10(max(A, B))) .

int
 gcdEuclidRemainderIter(int
 A,
 int B) {
    while
 (B !
=
 0) {
        A %
=
 B;
        swap(A,
 B);
    }
    return
 A;
}

А ето и едноредово, рекурсивно решение на последния алгоритъм:

int
 gcdEuclidRemainder(int
 A,
 int B) {
    return
 B =
=
 0
 ?
 A :
 gcdEuclidRemainder(B,
 A %
 B);
}

НОД на повече от две числа

НОД на повече от две числа можем да намерим като намерим НОД първо на първите две, после на тях и на следващото и т.н. Например за три числа имаме:

GCD({A,
 B,
 C}) =
 GCD(GCD(A,
 B),
 C);

По аналогичен начин можем да разширим алгоритъма за произволен брой числа.

Най-малко общо кратно

?	Ще отбелязваме най-малкото общо кратно на `A` и `B` `НОК(A, B)` или `LCM(A, B)`.

Най-малко общо кратно (Lowest Common Multiple) е най-малкото цяло положително число X, което се дели на дадени две числа A и B без остатък.

Дадени са две числа A и B. Да се намери най-малкото им общо кратно.

Наивният алгоритъм е с цикъл по отговора, което би значело да генерираме всички числа до A * B и да проверим дали A и B се делят едновременно на някое от тях. Този алгоритъм ще ни даде сложност O(A∙B).

long
 long
 lcmNaive(int
 A,
 int B) {
    for
 (long
 long
 i =
 max(A,
 B);
 i <
=
 (long
 long
)A *
 B;
 i+
+) {
        if
 (i %
 A =
=
 0
 &
&
 i %
 B =
=
 0) {
            return
 i;
        }
    }
}

Ефективен алгоритъм

Ако A и B са взаимно прости (т.е. имат НОД = 1), то LCM(A, B) = A * B. Иначе LCM(A, B) < A * B или по-точно LCM(A, B) = A * B / GCD(A, B). Допълнително можем да попроменим израза по следния начин за да намалим размера на междинните стойности: LCM(A, B) = A * (B / GCD(A, B)). Този алгоритъм ще ни даде сложност O(log10(max(A, B))) .

long
 long
 LCM(int
 A,
 int B) {
    return
 (long
 long
)A *
 (B /
 GCD(A,
 B));
}

НОК на повече от две числа

Както и за НОД, НОК на повече от две числа можем да намерим като намерим НОК първо на първите две, после на тях и на следващото и т.н. Например за три числа имаме:

LCM({A,
 B,
 C}) =
 LCM(LCM(A,
 B),
 C);

По аналогичен начин можем да разширим алгоритъма за произволен брой числа.

Разширен алгоритъм на Евклид

Както казахме в началото, алгоритъмът на Евклид за пресмятане на НОД произлиза от теоремата на Безу: ако имаме две неотрицателни цели числа A и B, които имат НОД D, то съществуват цели числа X и Y за които е изпълнено уравнението: A * X + B * Y = D. Понякога ни трябва не просто да намерим D, ами и самите коефициенти X и Y. За целта ползваме разширения алгоритъм на Евклид.

Имплементация

!	Забележете, че резултатите от алгоритъма могат да бъдат отрицателни!

Имплементацията е със същата сложност, както и намирането на НОД - O(log(max(A, B))) и, реално, не се различава много - единствено на всяка стъпка пазим малко повече допълнителна информация. Макар и да не ползваме деление с остатък, реално изважданията, които правим, са еквивалентни на това.

void
 extendedGCD(int
 A,
 int B) {
    long
 long
 currR =
 A,
 nextR =
 B;
    long
 long
 currS =
 1
,
 nextS =
 0
;
    long
 long
 currT =
 0
,
 nextT =
 1
;

    while (nextR) {
        long
 long
 quotient =
 currR /
 nextR;
        long
 long
 prevR =
 currR;
 currR =
 nextR;
 nextR =
 prevR -
 quotient *
 nextR;
        long
 long
 prevS =
 currS;
 currS =
 nextS;
 nextS =
 prevS -
 quotient *
 nextS;
        long
 long
 prevT =
 currT;
 currT =
 nextT;
 nextT =
 prevT -
 quotient *
 nextT;
    }

    fprintf(stderr
,
 "Greatest Common Divisor: %lld\n"
,
 currR);
    fprintf(stderr
,
 "Bézout coefficients: %lld %lld\n"
,
 currS,
 currT);
}

Multiplicative Inverse

Едно от най-честите приложения на разширения алгоритъм на Евклид е за да "делим" по модул. В повечето задачи, модулът M е просто число, което опростява делението, тъй като можем да ползваме факта, че A^M-1 = 1 (по модул M), от където следва, че A^M-2 = 1/A (по модул M). Така, за да разделим някакво число B на A по модул M просто умножаваме B * A^M-2, което е еквивалентно на B * 1 / A = B / A. Това, за съжаление, е вярно само когато модулът M е просто число - когато не е, трябва да прибегнем до разширения алгоритъм на Евклид.

В случай, че модулът M не е просто число, деление (наличие на multiplicative inverse) е възможно само за числа, които са взаимно-прости с модула. Това следва отново от теоремата на Безу: ако искаме A да има обратен елемент (multiplicative inverse), то трябва да съществува такова X, че A * X = 1 (по модул M). От теоремата имаме, че съществуват A * X + M * Y = GCD(A, M). Когато A и M са взаимно-прости, получаваме A * X + M * Y = 1 (mod M), което пък, тъй като е по модул M, можем да опростим до A * X = 1 (mod M).

Ще ползваме леко опростена версия на функцията extendedGCD(), която показахме по-горе:

int
 multiplicativeInverse(int
 A,
 int M) {
    long
 long
 currX =
 0
,
 nextX =
 1
;
    long
 long
 currR =
 M,
 nextR =
 A;

    while (nextR) {
        long
 long
 quotient =
 currR /
 nextR;
        long
 long
 prevX =
 currX;
 currX =
 nextX;
 nextX =
 prevX -
 quotient *
 currX;
        long
 long
 prevR =
 currR;
 currR =
 nextR;
 nextR =
 prevR -
 quotient *
 currR;
    }

    if
 (currR >
 1) {
        fprintf(stderr
,
 "Given number doesn't have multiplicative inverse module the given M.\n"
);
        return
 0
;
    }
    return
 (currX +
 M) %
 M;
}

Забележете, че на последния ред се справяме със случая, в който намереното обратно число е отрицателно.

Пример

Нека имаме модул M = 1,000,000. Можем да намерим "обратен" елемент само на числа, които не се делят на 2 и на 5 (тъй като ако имат някое от тях във факторизацията си, тоест се делят на тях, те не биха били взаимно-прости с 1,000,000).

Нека, например, искаме да разделим 1337 на 13 (по модул 1,000,000). Тоест резултатът 1337 / 13 = X трябва да е такъв, че X * 13 = 1337 (по модул 1,000,000). За целта трябва да намерим "обратното" число на 13 по този модул (така наречения multiplicative inverse), след което да умножим 1337 по него. Използвайки разширения алгоритъм на Евклид за 13 и 1,000,000 получаваме, че обратният елемент на 13 е 923077. Така намираме, че X = 1337 / 13 = 1337 * 923077 = 153949 (mod 1000000). Наистина, 153949 * 13 = 1337 (по модул 1,000,000).

Задачи за тренировка

Референции

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 25167 пъти.