Programare Competitivă

Aritmetica modulară

Aritmetica modulară e aritmetica pe resturi. Când spui “a mod m” te referi la restul împărțirii lui a la m.

Apare peste tot în programare competitivă: când rezultatul poate fi foarte mare (10^18 sau mai mare), cerința e de obicei să-l dai modulo un număr prim - de exemplu 10^9 + 7.

Operatorul % în C++

int a = 17;
int b = 5;
cout << a % b; // 2 (17 = 3*5 + 2)

Reguli:

  • a % b returnează restul împărțirii
  • a % b are semnul lui a (în C++)
  • a % b = 0 ⟺ b divide a

Proprietăți fundamentale

Pentru orice a, b, m:

(a + b) mod m = ((a mod m) + (b mod m)) mod m

(a - b) mod m = ((a mod m) - (b mod m) + m) mod m

(a * b) mod m = ((a mod m) * (b mod m)) mod m

De ce e util? Dacă a și b sunt mari (risc de overflow), le putem reduce modulo m pe parcurs.

Exemplu

Vrem (12345678 * 98765432) mod 1000.

Cu overflow: 12345678 * 98765432 = ... depășește int ușor.

Cu mod pe parcurs:

12345678 mod 1000 = 678
98765432 mod 1000 = 432
(678 * 432) mod 1000 = 293056 mod 1000 = 56

Overflow și long long

În C++, int acoperă doar până la ~2*10^9. Pentru înmulțiri e risc de overflow.

int a = 1000000;
int b = 1000000;
int c = a * b;       // OVERFLOW - c devine un număr negativ aiurea

long long c2 = a * b; // TOT OVERFLOW - multiplicația e in int inainte de atribuire!

long long c3 = (long long)a * b; // CORECT - cast la long long inainte

Regulă de siguranță: pentru mod, folosește long long pentru toate variabilele implicate în calcul.

Scăderea modulară

În C++, a - b poate fi negativ. Atunci (a - b) % m dă un rezultat negativ (în C++).

long long rezultat = (a - b) % MOD; // poate fi negativ!

// CORECT:
long long rezultat = ((a - b) % MOD + MOD) % MOD;

Adăugarea unui MOD garantează că rezultatul e pozitiv.

Dacă a - b poate fi și mai negativ (de exemplu din mai multe scăderi), adaugă mai mult:

long long rezultat = ((a - b) % MOD + 2*MOD) % MOD;

Codul tipic

const long long MOD = 1000000007; // 10^9 + 7

long long add(long long a, long long b) {
    return (a + b) % MOD;
}

long long sub(long long a, long long b) {
    return ((a - b) % MOD + MOD) % MOD;
}

long long mul(long long a, long long b) {
    return (a * b) % MOD;
}

Aceste funcții pot fi folosite peste tot unde faci operații modulo.

De ce 10^9 + 7?

E un număr prim suficient de mare, iar (10^9 + 7)^2 < 2^63 - deci long long * long long mod 10^9+7 nu depășește long long (max ~9.2 * 10^18).

Alte alegeri populare:

  • 998244353 (prim, util pentru FFT modular)
  • 10^9 + 9

Împărțirea modulară și inversul modular

Aritmetica modulară cu +, -, * e simplă. Dar împărțirea e mai delicată.

(a / b) mod m ≠ ((a mod m) / (b mod m)) mod m în general!

În schimb, folosim inversul modular: cel mai mic b^(-1) pentru care b * b^(-1) ≡ 1 (mod m).

Atunci:

a / b ≡ a * b^(-1) (mod m)

Calculul inversului modular

Dacă m e prim și gcd(b, m) = 1, prin mica teoremă a lui Fermat:

b^(m-1) ≡ 1 (mod m) ⟹ b^(-1) ≡ b^(m-2) (mod m)

Calculăm b^(m-2) cu exponentiere rapidă în O(log m).

long long putereModulo(long long baza, long long exp, long long m) {
    long long rez = 1;
    baza %= m;
    while (exp > 0) {
        if (exp & 1) rez = rez * baza % m;
        baza = baza * baza % m;
        exp >>= 1;
    }
    return rez;
}

long long invers(long long a) {
    return putereModulo(a, MOD - 2, MOD);
}

long long div_mod(long long a, long long b) {
    return a * invers(b) % MOD;
}

Atenție: inversul modular există doar dacă gcd(b, m) = 1. Dacă m e prim, asta e garantat pentru orice b care nu e multiplu de m.

Problemă clasică: număr de combinări modulo

Combinări C(n, k) = n! / (k! * (n-k)!). Pentru n = 10^5, C(n, k) e imens.

Precalculăm factorialele și inverselele lor modulo:

const int MAXN = 100001;
long long fact[MAXN], invFact[MAXN];

void precalculare() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i-1] * i % MOD;

    invFact[MAXN-1] = putereModulo(fact[MAXN-1], MOD-2, MOD);
    for (int i = MAXN-2; i >= 0; i--)
        invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

Precalculare: O(n). Interogare C(n, k): O(1).

Cod complet: exemplu

Calculăm (a + b) și (a * b) modulo 10^9 + 7.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const long long MOD = 1000000007;

int main()
{
    long long a, b;
    fin >> a >> b;

    fout << (a + b) % MOD << "\n";
    fout << ((a - b) % MOD + MOD) % MOD << "\n";
    fout << (a * b) % MOD << "\n";

    return 0;
}

date.in:

999999999999 999999999998

date.out:

999999985
1
48

Pas cu pas: calculăm C(5, 2) mod 7

C(5, 2) = 5! / (2! * 3!) = 120 / 12 = 10, iar 10 mod 7 = 3.

Precalculare fact (mod 7)

  • fact[0] = 1
  • fact[1] = 1
  • fact[2] = 2
  • fact[3] = 6
  • fact[4] = 24 mod 7 = 3
  • fact[5] = 5*3 mod 7 = 15 mod 7 = 1

Inversele

  • Fermat: b^(-1) ≡ b^(7-2) = b^5 (mod 7)
  • invFact[5] = 1^5 = 1
  • invFact[4] = invFact[5] * 5 = 5
  • invFact[3] = invFact[4] * 4 = 20 mod 7 = 6
  • invFact[2] = invFact[3] * 3 = 18 mod 7 = 4
  • invFact[1] = invFact[2] * 2 = 8 mod 7 = 1
  • invFact[0] = invFact[1] * 1 = 1

Calcul C(5, 2)

fact[5] * invFact[2] * invFact[3] = 1 * 4 * 6 = 24 mod 7 = 3 ✓

Proprietăți geniale ale mod

1. Congruența

a ≡ b (mod m) înseamnă a mod m = b mod m (sau echivalent, m | (a - b)).

17 ≡ 5 (mod 6)
24 ≡ 0 (mod 8)

2. Operațiile se transmit

Dacă a ≡ a' (mod m) și b ≡ b' (mod m):

  • a + b ≡ a' + b' (mod m)
  • a * b ≡ a' * b' (mod m)

Asta legitimează tot ce am spus.

3. mod nu comută cu / sau ^

  • (a^b) mod m ≠ (a mod m)^(b mod m) mod m
  • Pentru puteri, reduce doar baza: (a mod m)^b mod m

Greșeli frecvente

1. Overflow la înmulțire

long long a = 1e9, b = 1e9;
long long c = a * b % MOD; // CORECT daca a, b < MOD
long long c = a + b;        // OK

int x = 1e9, y = 1e9;
long long c = x * y;        // OVERFLOW! x * y se face in int
long long c = (long long)x * y; // CORECT

2. Scădere negativă

long long diff = (a - b) % MOD; // NEGATIV in C++!

// CORECT:
long long diff = ((a - b) % MOD + MOD) % MOD;

3. Inversul modular pentru m nu prim

Dacă m nu e prim, nu poți folosi Fermat. Folosește algoritmul lui Euclid extins pentru a calcula inversul.

4. Inversul lui 0

0^(-1) mod m nu există. Nu încerca să împarți la 0 modular.

5. Pentru operații simple, folosește funcții

Evită să scrii (... + ... * ... + MOD) % MOD prin cod. Folosește funcții add, mul, sub - mai puține bug-uri.

Ce să reții

  • Aritmetica modulară = aritmetica pe resturi, apare peste tot în probleme cu numere mari.
  • Operațiile +, -, * se distribuie prin mod: (a op b) mod m = ((a mod m) op (b mod m)) mod m.
  • Scăderea: adaugă MOD înainte de % MOD pentru a evita rezultate negative.
  • Folosește long long pentru a evita overflow.
  • Împărțirea necesită invers modular: a/b ≡ a * b^(-1) (mod m), iar b^(-1) = b^(m-2) mod m dacă m e prim.
  • Modulul standard: 10^9 + 7 (prim, evită overflow la long long).
  • Precalculează factoriale și inverse pentru combinări rapide în O(1).
Cuprins Inapoi Inainte