Модулна аритметика

Modular Arithmetics

В тази тема ще видим какво представлява модулната аритметика и защо тя е важна за състезанията по програмиране. Ще разгледаме как се извършват основните операции (събиране, изваждане, умножение, деление) и за какво да внимаваме когато я ползваме.

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

Какво е аритметика по модул?

?	Един пример за модулна аритметика, с който сте се сблъскали още като деца, е начинът, по който отбелязваме времето: часовете са по модул 24, а минутите - по модул 60.

Аритметиката по модул, или "модулна аритметика", както ще я срещате по-често, представена по-просто, е "циклична" целочислена аритметика. При нея първо избираме какъв лимит на числата искаме да наложим (наричан "модул" или "modulus" на английски). Нека кажем, че това е числото MOD. Всички числа в тази аритметика ще са в интервала [0, MOD-1].

Когато някое число стане твърде голямо в следствие на някоя операция (например събиране или умножение) то "превърта" и се връща обратно в интервала. За целта, просто взимаме остатъка при деление на модула.

!	В повечето програмни езици, операцията "взимане на остатък при деление" се прави с оператора '%'. Така, например, остатъкът на 42 при деление на 17 можем да намерим с `42 % 17 = 8`.

Да кажем, при MOD = 17, числото 42 ще бъде 8 (тъй като остатъкът на 42 при деление на 17 е 8).

Същото правим и ако числото стане твърде малко. В момента, в който получим отрицателно число, трябва отново да го върнем в интервала [0, MOD-1]. За целта можем да добавяме MOD към него, докато стане по-голямо или равно на нула. Забележете, че добавяйки MOD към което и да е отрицателно число отново и отново, рано или късно ще го "вкара" в диапазона [0, MOD-1]. Например -42 при MOD = 17 ще бъде 9, тъй като:

-42 + 17 = -25
-25 + 17 = -8
-8 + 17 = 9

Както ще видим малко по-късно, ако числата, които изваждаме, вече са по модул, и едно-единствено добавяне на MOD би ни свършило работа.

Примери

Нека разгледаме няколко примера.

Ако извършваме операциите по модул MOD = 100, то 42 + 77 = 119 = 19 (mod 100). Произведението 131 по 17 пък е 131 * 17 = 2227 = 27 (mod 100). При изваждането трябва да внимаваме дали резултатът е отрицателен, в който случай да го върнем обратно в ограниченията. Например, 50 - 32 = 18 (mod 100), но 32 - 50 = -18 = 82 (mod 100).

В случая, това, че модулът е 100, е относително "удобно" за нас - при операциите просто взимаме последните две цифри на резултата. Често, обаче, модулите, с които трябва да работим (например, са ни наложени в задачата), не са "кръгли" числа (след малко ще видим и защо).

Така, ако имаме MOD = 54321, то 50505 + 42666 = 93171 = 38850 (mod 54321). Умножението 50505 * 42666 = 2154846330 = 40902 (mod 54321).

Забележете, че макар модулът да е доста малък, междинните сметки могат да доведат до относително големи числа. В случая, ако ползваме int, числото 2154846330 би overflow-нало и бихме получили грешен резултат. Това е много честа грешка при начинаещите програмисти, затова изрично сме я споменали няколко пъти в темата.

Начални числа, по-големи от модула

Не е задължително началните числа да са в интервала [0, MOD-1]. Без проблем можем първо да ги вкараме в този интервал, след което да извършим операциите. Това ще доведе до същия резултат, както и ако първо извършим операциите, а после направим модула.

Например, 123456789 * 987654321 = 121932631112635269 = 13284 (mod 54321). Също така, обаче, 123456789 = 39477 (mod 54321), 987654321 = 44220 (mod 54321), и 39477 * 44220 = 1745672940 = 13284 (mod 54321).

Прости модули

Най-често за модул се ползва просто число. Причини за това има много (във висшата алгебра в университета се изучава защо - получава се крайно поле), като тук ще разгледаме двете най-основни.

При умножение рядко се получава нула

Често в задачи с модул се налага да изчислим произведението на много на брой числа (съответно, резултатът става голям и се налага да се ползва модул). Ако модулът не е прост, обаче, ако на (която и да е) стъпка получим нула, от там нататък тя ще си остане нула до края. Така голяма част от възможните входове на задачата биха имали резултат нула.

Гарантирано е, че ако X * Y = 0, то или X = 0, или Y = 0, или X =Y = 0. Алтернативно, ако X != 0 и Y != 0, то X * Y != 0.

Ако модулът не е прост, например MOD = 42, то, да кажем, 14 * 12 = 168 = 0 (mod 42). Всъщност, произволно разбиване на модула на делители, потенциално умножени по други числа, би дала 0 (например 7 * 6, 2 * 21, 3 * 28, ...). Тъй като, обаче, простите числа нямат валидно разбиване на делители по модул самите себе си, това няма как да се случи при тях.

По-просто деление

Има относително лесен начин да извършваме деление (както ще видим по-долу).

Операции

Нека разгледаме в малко повече детайли стандартните аритметични операции: събиране, изваждане, умножение и деление.

Събиране

Както показахме и по-горе, няма нищо особено при събирането. Ако двете числа, които събираме, са вече по модул, то знаем, че никое от тях не е отрицателно, съответно не е нужно да правим проверка дали резултатът е по-малък от нула:

int
 modAdd(int
 num1,
 int num2) {
    return
 (num1 +
 num2) %
 MOD;
}

Фактът, че и двата аргумента са по-малки от MOD, означава, че сумата им ще е по-малка от 2 * MOD. Като малка оптимизация можем да си спестим една операция '%' (която е тежка колкото деление, тоест забележимо по-бавна от събиране и изваждане) правейки следното:

int
 modAdd(int
 num1,
 int num2) {
    int
 res =
 num1 +
 num2;
    return
 res >
=
 MOD ?
 res -
 MOD :
 res;
}

Така заменихме едно деление с един if() и едно изваждане, което на практика е малко по-бързо. Все пак, когато скоростта не е от огромно значение, е по-добре да ползвате стандартната имплементация.

Изваждане

Трябва да извършим изваждането по такъв начин, че резултатът да остане в [0, MOD-1]. Ако двете числа, които изваждаме, са вече по модул, то разликата или ще е неотрицателно число в правилния интервал, или число в [1-MOD, -1]. Тук можем да забележим, че във втория случай не е нужно да добавяме MOD "отново и отново" докато стигнем до правилния интервал - трябва да го добавим точно веднъж.

int
 modSub(int
 num1,
 int num2) {
    int
 res =
 num1 -
 num2;
    return
 res >
=
 0
 ?
 res :
 res +
 MOD;
}

Можем да елиминираме частния случай като забележим, че MOD = 0 (mod MOD), като винаги добавяме MOD към разликата, но извършваме и деление с остатък след това:

int
 modSub(int
 num1,
 int num2) {
    return
 (num1 -
 num2 +
 MOD) %
 MOD;
}

Наистина, ако num1 е по-голямо или равно на num2 число, то ще получим, например, (17 - 13 + 42) % 42 = (17 - 13) % 42 = 4 (mod 42). Ако пък num1 е по-малко от num2 бихме имали (13 - 17 + 42) % 42 = 38 (mod 42).

Умножение

Умножението не е много различно от събирането, но резултатите могат да са значително по-големи. Това води до следните две основни разлики:

Вече не можем да ползваме оптимизацията с if()-а, тъй като нищо не ни гарантира, че резултатът ще е в [0, 2 * (MOD-1)].
Макар и крайният резултат да е относително малък (до MOD-1), може междинните сметки да станат големи. Тоест, трябва да внимаваме да не стигнем до overflow.

Втората разлика е много важна, тъй като често е проблем при по-неопитните състезатели.

За да се справим с проблема трябва да видим дали MOD * MOD се побира в типа, с който работим.

?	Някои състезатели предпочитат просто да ползват през цялото време `long long`, въпреки, че модулът се побира в `int`. Така те премахват възможността да се получи overflow, на цената на двойно повече ползвана памет и малко по-бавни операции.

Най-често това не е така. Много често, например, MOD = 1000000007, което, само по себе си, се побира в int, но едно умножение на две числа от този порядък е далеч над това, което можем да съберем в един int. Решението на този проблем е да ползваме по-голям тип за самото умножение, а връщаният резултат да е от малкия тип:

int
 modMul(int
 num1,
 int num2) {
    return
 ((long
 long
)num1 *
 num2) %
 MOD;
}

Тук ползваме long long, който е 64-битов, за да извършим умножението, а след това с модула върнахме числото обратно в достатъчно малки размери, за да го върнем от функцията като int.

Деление

Делението на пръв поглед е проблематично. Тъй като искаме операциите да са "обратими" (изваждането да е обратната операция на събирането, а делението - да е обратната на умножението), то трябва да го дефинираме по такъв начин, че това да е изпълнено. Тоест, трябва да го направим по такъв начин, че ако X / Y = Z, за три числа X, Y, Z от [1, MOD-1], то Z * Y = X. Разбира се, делението на нула не е дефинирано, както и всяко число, умножено по нула, трябва да даде нула.

Стандартното деление не може да бъде приложено тук, тъй като е "целочислено", тоест без остатък, което автоматично го прави необратимо. Да кажем, 17 / 3 = 5, но 5 * 3 != 17. Нецелочислено деление също не може да бъде приложено, тъй като искаме модулната аритметика да е само с цели числа.

Ако модулът не е просто число, лесно можем да намерим произведение, което не е "обратимо". Например, нека имаме модул MOD = 123. Ако разгледаме произведението 10 * 12 = 120 (mod 123), то би трябвало 120 / 12 = 10. В същото време, обаче, 51 * 12 = 120 (mod 123), тоест би трябвало и 120 / 12 = 51. Това няма как да се случи едновременно, тоест операцията не е обратима.

Както споменахме по-горе в темата, простият модул ни помага да дефинираме деление. Всъщност, вместо да делим на X можем да умножаваме по 1/X, което е еквивалентно. Нека разгледаме, например, MOD = 11. За всяко (ненулево) число можем да намерим негово реципрочно по този модул: 1/1 = 1, 1/2 = 6, 1/3 = 4, 1/4 = 3, 1/5 = 9, 1/6 = 2, 1/7 = 8, 1/8 = 7, 1/9 = 5, 1/10 = 10. Наистина, можем да видим, че ако искаме да разделим, например, на 3, можем да умножаваме по 4 (неговото реципрочно) и получаваме точно отговорите, които очакваме:

0 / 3 = 0 * 4 = 0 = 0 (mod 11)
3 / 3 = 3 * 4 = 12 = 1 (mod 11)
6 / 3 = 6 * 4 = 24 = 2 (mod 11)
9 / 3 = 9 * 4 = 36 = 3 (mod 11)

Можете да се уверите, че и сметките с останалите числа (и техните реципрочни) работят както очаквате.

Нещо повече, дори ако числата не се делят "точно", тоест се получава остатък, делението е дефинирано така, че все пак да е обратимо (тоест, все едно работите с нецели числа!):

10 / 3 = 10 * 4 = 40 = 7 (mod 11) и обратно, 7 * 3 = 21 = 10 (mod 11)
7 / 2 = 7 * 6 = 42 = 9 (mod 11) и обратно, 9 * 2 = 18 = 7 (mod 11)
8 / 5 = 8 * 9 = 72 = 6 (mod 11) и обратно, 6 * 5 = 30 = 8 (mod 11)

Магия!

Сега остава въпросът как точно да намерим тези реципрочни? От малката теорема на Ферма знаем, че когато модулът е прост, за всяко число X в [0, MOD-1] е изпълнено, че X^MOD = X (mod MOD). Това значи, че X^MOD-1 = 1 (mod MOD), и, съответно, X^MOD-2 = 1/X (mod MOD). Единственият проблем тук е, че ако модулът е голямо число (примерно 1,000,000,007) ще трябва да вдигнем X на много голяма степен: 1,000,000,005. За щастие, както ще видим в темата за бързо вдигане на степен, можем да направим това доста ефективно относително лесно.

Така делението (при прост модул) изглежда по следния начин:

int
 fastPow(int
 num,
 int pwr) {
    int
 ret =
 1
;
    for
 (;
 pwr >
 0
;
 pwr >
>
=
 1) {
        if
 (pwr &
 1)
            ret =
 ((long
 long
)ret *
 num) %
 MOD;
        num =
 ((long
 long
)num *
 num) %
 MOD;
    }
    return
 ret;
}

int
 modDiv(int
 num1,
 int num2) {
    return
 modMul(num1,
 fastPow(num2,
 MOD -
 2
));
}

Тук функцията fastPow(int num, int pwr) вдига числото num на pwr-та степен (за O(log(pwr)) време).

Асоциативност и комутативност

Операциите при модулната аритметика, също както и при стандартната такава, са асоциативни и комутативни.

Асоциативност

Асоциативността е свойството резултатът да не зависи от реда на изчисляване на израз в който дадена операцията участва повече от веднъж. Например, A + B + C = (A + B) + C = A + (B + C)

Комутативност

Комутативност пък е свойството резултатът да остава непроменен при размяна на местата на някои от операндите. Например, A + B + C = B + A + C = C + B + A.

Допълнение

Интересно следствие на това, че извършваме делението чрез умножение, е, че следните равенства също са изпълнени:

A * B / C = (A * B) / C = A * (B / C)
A * B / C = B * A / C = A / C * B = B / C * A

Чести грешки

Чести грешки, които се допускат при ползването на модулна аритметика, са:

Да не се ползва по-голям тип при умножение
Да не се приведат началните числа по модул (ако не са)
Да не се разглежда случая, в който резултатът от дадена операция е отрицателен (когато трябва да се "приведе" отново до [0, MOD-1])
Да се извършват по няколко операции наведнъж без да се модва (например (A * B * C) % MOD вместо (((A * B) % MOD) * C) % MOD или пък (A - B - C + MOD) % MOD вместо ((A - B + MOD) % MOD - C + MOD) % MOD) в който случай временните резултати може да overflow-нат или да станат твърде малки за да работи (X + MOD) % MOD за вкарването им обратно в границите

Последната от изброените чести грешки се решава доста чисто, като операциите се изведат във функции (както показахме в примерния код в темата).

Сигурно умножение

В началото на темата казахме, че често се налага да ползваме по-голям тип при умножение по модул, тъй като резултатът от умножението може да overflow-не. Какво става, обаче, ако модулът е много голям (примерно около 10¹⁸) и нямаме по-голям тип, който да можем да ползваме? На помощ идва нещо, което ще наречем "бавно умножение". То е модификация на бързото вдигане на степен, и ще разгледаме в съответната тема.

Употреба

Модулната аритметика е особено често срещана в състезателни задачи, когато отговорът може да стане потенциално много голям, но авторите на задачата не искат да се ползват дълги числа. Често, това се случва когато задачата е комбинаторна или ползва динамично оптимиране, или пък се ползва вдигане на матрица на степен (например, за намиране на брой различни пътища с фиксирана дължина).

Тъй като писането (и ползването) на дълги числа не допринася за "готината" част от решаване на задачата (нейното измисляне), но в същото време прави сметките по-бавни, а изхода - по-голям, почти винаги то се избягва в полза на модулна аритметика. Можете да се уверите в това, като проверите задачите през последните 10 години на произволно състезание (български национални, TopCoder, Codeforces...) - броят задачи с модул към броя задачи с дълги числа е нещо от сорта на 20:1 до 50:1.

Референции

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

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