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

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, тъй като:
  1. -42 + 17 = -25
  2. -25 + 17 = -8
  3. -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).

Умножение

Умножението не е много различно от събирането, но резултатите могат да са значително по-големи. Това води до следните две основни разлики:
  1. Вече не можем да ползваме оптимизацията с if()-а, тъй като нищо не ни гарантира, че резултатът ще е в [0, 2 * (MOD-1)].
  2. Макар и крайният резултат да е относително малък (до 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] е изпълнено, че XMOD = X (mod MOD). Това значи, че XMOD-1 = 1 (mod MOD), и, съответно, XMOD-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-не. Какво става, обаче, ако модулът е много голям (примерно около 1018) и нямаме по-голям тип, който да можем да ползваме? На помощ идва нещо, което ще наречем "бавно умножение". То е модификация на бързото вдигане на степен, и ще разгледаме в съответната тема.

Употреба

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

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

Референции

  1. Modular Arithmetic (en.wikipedia.org)
  2. Finite Field (en.wikipedia.org)
  3. Modular Multiplicative Inverse (en.wikipedia.org)
  4. Fermat's Little Theorem (en.wikipedia.org)
  5. Бързо вдигане на степен (informatika.bg)


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

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: