Aritmetică modulară — calcule fără overflow

De ce avem nevoie de modulo

La multe probleme de combinatorică rezultatul crește exploziv: numărul de moduri de a aranja ceva poate avea sute de cifre. Niciun tip de date nu ține așa ceva. De aceea enunțul cere des: „afișați rezultatul modulo un număr”.

Ideea: în loc să ții numărul uriaș, ții doar restul lui la împărțirea cu m. Restul încape mereu între 0 și m-1, deci nu crește niciodată. Standardul la concurs este:

const long long MOD = 1000000007;   // 1e9 + 7, un numar prim

Vestea bună: trei operații se „distribuie” peste modulo, adică poți reduce oricând fără să strici rezultatul:

• Adunare: (a + b) % m == ((a % m) + (b % m)) % m
• Scădere: (a - b) % m == ((a % m) - (b % m) + m) % m
• Înmulțire: (a * b) % m == ((a % m) * (b % m)) % m

Le aplici la fiecare pas, nu doar la final — așa ții numerele mereu mici.

Exemplu pas cu pas

Să calculăm (987654 * 123456 * 555) % 1000 reducând la fiecare pas. Folosim m = 1000, deci ne interesează doar ultimele 3 cifre.

• Pornim: 987654 % 1000 = 654
• Înmulțim cu 123456: mai întâi 123456 % 1000 = 456, apoi 654 * 456 = 298224, iar 298224 % 1000 = 224
• Înmulțim cu 555: 224 * 555 = 124320, iar 124320 % 1000 = 320

Rezultat: 320. Numerele intermediare au rămas mici (sub un milion).

Dacă în schimb am fi înmulțit întâi totul: 987654 * 123456 * 555 depășește de departe limita lui long long (peste 9.2 · 10¹⁸) → overflow, valoare greșită. Tocmai de asta reducem la fiecare pas.

Implementare C++

Atenție la înmulțire: chiar dacă a și b sunt mai mici decât m ≈ 10⁹, produsul a * b ajunge la 10¹⁸ — peste limita lui int. Folosim long long.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;   // 1e9 + 7, prim

// normalizeaza un rest in intervalul [0, MOD-1]
long long norm(long long a) {
    return ((a % MOD) + MOD) % MOD;   // trateaza si a negativ
}

long long addmod(long long a, long long b) {
    return norm(a + b);               // ex: addmod(7, 5) cu MOD mic
}

long long submod(long long a, long long b) {
    return norm(a - b);               // ex: submod(2, 5) -> NU iese negativ
}

long long mulmod(long long a, long long b) {
    // a si b pot fi pana la ~1e9; a*b incape in long long (max ~9.2e18)
    return norm(a * b);
}

int main() {
    long long a = 987654, b = 123456, c = 555;

    long long s = addmod(a, b);       // (987654 + 123456) % MOD = 1111110
    long long d = submod(a, b);       // (987654 - 123456) % MOD = 864198
    long long p = mulmod(mulmod(a, b), c);  // produs redus pas cu pas

    cout << s << "\n";                // 1111110
    cout << d << "\n";                // 864198
    cout << p << "\n";                // restul lui a*b*c modulo MOD

    // demonstratie modulo negativ nenormalizat vs normalizat
    cout << (-7 % 3) << "\n";         // poate afisa -1 (depinde de compilator)
    cout << norm(-7) << "\n";         // cu MOD aici e MOD-7; ideea: mereu pozitiv

    return 0;
}

Complexitate

Fiecare operație — addmod, submod, mulmod, norm — face un număr fix de adunări, înmulțiri și %. Deci fiecare costă O(1). Dacă reduci în interiorul unei bucle cu n pași, costul total e O(n) — la fel ca bucla, fără penalizare.

Ceasul modulo 12: pornind de la ora 10 și adunând 5, treci de 11, te „rotești” la 0 și ajungi la ora 3. Adică (10 + 5) % 12 = 3.

Vizualizare

Recapitulare

• Ții doar restul la MOD = 1000000007; adunarea, scăderea și înmulțirea se distribuie, așa că reduci cu % MOD la fiecare pas ca să eviți overflow.
• La înmulțire folosește long long (produsul ajunge la 10¹⁸) și normalizează orice rest cu ((a % m) + m) % m ca să nu rămână negativ.
• Împărțirea nu se distribuie peste modulo — pentru ea ai nevoie de invers modular (lecția „invers-modular”).