De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?
Cel mai cu seamă ai rezolvat o problemă de informatică (cum ar fi de
combinatorică sau de programare dinamică) și în cerința acesteia apărea
mențiunea de a afișa răspunsul modulo 666013
, modulo 1.000.000.007
,
modulo 123457
sau un alt număr foarte ciudat (care pare ales la întâmplare).
Această mențiune nu este una făcută la întâmplare, ci ajută foarte mult la
implementarea problemei și la verificarea acesteia.
De ce se cere răspunsul modulo un număr mare?
Răspunsul pentru anumite probleme poate fi uriaș. Spre exemplu, dacă vrem să
calculăm n!
(factorialul unui număr n
), trebuie să înmulțim pe rând
numerele 1
, 2
, 3
, …, n
, număr ce poate avea un număr uriaș de cifre.
Doar factorialele până la 12!
încap în tipul de date int
, iar doar până la
20!
încap în tipul de date long long
.
Astfel, o problemă care cere calcularea numărului de permutări al unei
mulțimi, de pildă, se așteaptă la calcularea valorii n!
, unde n
este
lungimea mulțimii. Prin urmare, există doar câteva opțiuni la care poate să
recurgă creatorul unei probleme:
- să folosească valori mici pentru
n
(n ≤ 20
), ca să se utilizeze tipurile de dateint
saulong long
, care ar face problema prea ușoară; - să implementeze soluția pe numere mari care să afișeze răspunsul exact pentru valori mai mari de
20
, lucru ce ar încetini considerabil programul și l-ar complica fără rost; - să folosească un alt artificiu care să poată folosi tipurile de date cunoscute dar să accepte și numere mai mari de
20
.
Artificiul care se poate utiliza în acest caz este efectuarea operațiilor pe
aritmetica modulară. Mai exact, toate operațiile pe care le facem (adunări,
scăderi, înmulțiri, împărțiri, etc.) se realizează modulo
un anumit număr
mai mare mod
, dar care încape în int
. În acest fel, mereu vom avea un
răspuns între 0
și mod - 1
.
Mai mult decât atât. Există cazuri în care dacă efectuăm operații modulo mod
, vom ajunge într-un final la răspunsul 0
, lucru ce ar însemna că dacă
cineva nu știe să rezolve o problemă, ar putea afișa 0
și ar primi un pic de
punctaj pe testele care au ca răspuns 0
. Pentru a evita acest lucru, numărul
mod
trebuie să fie prim.
De ce se aleg valori aleatorii? De ce nu modulo 10000?
Valorile alese pentru mod
nu sunt aleatorii. Acestea trebuie să
îndeplinească condițiile:
- să fie foarte mari;
- să fie numere prime;
- să fie ușor de reținut (pentru a evita încurcăturile).
Din acest motiv se folosesc cel mai des următoarele numere pentru mod
:
666013
, 1.000.000.007
, 123457
, 777013
, 1.000.000.009
și altele.
Și totodată de aceea nu apar numere mai obișnuite, precum puteri de 10
(1000
, 100.000
, etc.) sau alte numere.
Cum se aplică operațiile modulo 666013
?
Operațiile modulo 666013
(sau alt număr) nu sunt foarte dificile. Pentru
generalizare, numim valoarea la care se calculează restul mod
. Iată cum se
fac operațiile obișnuite.
Adunarea modulară
Adunarea este foarte simplă. Operația s = x + y
în modulo
este:
//Opțiunea 1
s = (x + y) % mod;
Sau, mai sigur, ca să ne asigurăm că nu ieșim din tipurile de date:
//Opțiunea 2. Îl facem long long și aplicăm modulo la toate numerele
s = (1ll * (x % mod) * (y % mod)) % mod;
Scăderea modulară
Scăderea este asemănătoare, însă trebuie avut grijă atunci când rezultatul
ajunge negativ (ceea ce este un lucru obișnuit în aritmetica modulară). Ne
amintim că rezultatul trebuie să fie între 0
și mod - 1
, deci adunăm un
mod
dacă este nevoie.
//Opțiunea 1
dif = x - y;
while(dif < 0) {
dif = dif + mod;
}
Sau, dintr-o singură linie:
//Opțiunea 2. Adunăm direct mod
dif = (x - y + mod) % mod;
Înmulțirea modulară
Înmulțirea este similară cu adunarea. Dacă vrem să aplicăm p = x * y
, avem:
//Opțiunea 1
p = (x * y) % mod;
Sau a doua opțiune, mai sigură:
//Opțiunea 2
p = (1ll * (x % mod) * (y % mod)) % mod;
Împărțirea modulară
Împărțirea modulară poate fi mai complicată. Să zicem că vrem să facem
împărțirea 666014 / 2 modulo 666013
. Răspunsul pare simplu, e 333007 modulo 666013
, adică 333007
. Dar dacă facem cum am făcut până acum, adică (666014 % 666013) / (2 % 666013)
, avem 1 / 2
, adică un număr cu virgulă, care este
clar diferit de răspunsul corect 333007
.
Așadar, nu acesta este răspunsul. Defapt, împărțirea de tip n = x / y
este
echivalentă cu n = x * puterelog(y, mod - 2)
. Funcția puterelog
este
ridicarea la putere, care trebuie implementată în timp
logaritmic pentru eficiență și totodată trebuie realizată modulo mod
.
n = x * puterelog(y, mod - 2);
Alte operații pe aritmetică modulară
Alte operații se pot dezvolta după cele menționate mai sus. De pildă, calculul combinărilor, aranjamentelor, permutărilor, etc. se implementează cu ușurință folosind aceste reguli.
Alte resurse și bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0