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 date int sau long 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

• Aritmetica modulară - PbInfo
• Modular arithmetic - Wikipedia