Adunare modulo — AlgoClar

De ce contează?

Pe un ceas, dacă e ora 10 și aștepți 5 ore, nu ajungi la ora 15 — ajungi la ora 3. Acele au făcut o tură completă și au luat-o de la capăt. Adunarea modulo e exact acest fel de adunare „în cerc", unde numerele se întorc la zero când ating modulul.

Regula adunării modulo

Proprietatea fundamentală e că modulo se distribuie peste adunare:

(a + b) % m = (a % m + b % m) % m

Cu alte cuvinte, poți reduce fiecare termen modulo m înainte să-l aduni, iar rezultatul rămâne același. Pe ceasul de 12: 10 + 5 = 15, iar 15 % 12 = 3.

Observația-cheie

De ce mai aplici % m la final, dacă termenii erau deja reduși? Pentru că suma a două resturi (fiecare sub m) poate ajunge până la 2m − 2, deci poate depăși m. Un ultim % m o readuce în intervalul corect.

De ce reducem pe parcurs

Dacă aduni mii de numere și vrei rezultatul modulo m, ai două variante: aduni tot și aplici % m la final, sau reduci după fiecare adunare. Matematic dau același lucru — dar a doua variantă ține numerele mici și evită overflow-ul.

Exemplu: aduni 100.000 de valori, fiecare aproape de 10⁹. Suma reală ar ajunge la 10¹⁴, mult peste int. Reducând modulo după fiecare pas, valoarea nu trece niciodată de m.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    const int MOD = 1000000007;
    int v[] = {900000000, 800000000, 700000000};
    int n = 3;

    int suma = 0;
    for (int i = 0; i < n; i++) {
        suma = (suma + v[i]) % MOD;  // reducem la fiecare pas
    }

    cout << suma << "\n";  // (2400000000) % MOD = 399999979
    return 0;
}

Aici suma + v[i] ajunge cel mult la 2·(MOD−1) ≈ 2×10⁹, ceea ce încă încape în int — la limită. Dacă modulul ar fi mai mare, ai folosi long long pentru siguranță.

Complexitate

Fiecare adunare modulo costă O(1). Adunarea modulo a n termeni rulează în O(n) — o singură parcurgere, cu numerele menținute mici tot timpul.

Vizualizare

Urmărește cum valoarea se rotește înainte pe cadran și se reia de la 0 după fiecare tură de m pași — adunarea modulo e chiar mersul acelor pe ceas:

Greșeli frecvente

Greșeala 1 — aduni tot și aplici % m abia la final: suma intermediară poate depăși tipul și să dea overflow înainte de a ajunge la %. Redu după fiecare adunare.

Greșeala 2 — uiți % m final după ce ai redus termenii: (a % m + b % m) poate fi încă ≥ m. Mai trebuie un % m.

Greșeala 3 — tip prea mic: dacă 2·MOD nu încape în int, suma a două resturi dă overflow. Când modulul e mare, folosește long long.

Greșeala 4 — presupui rezultat pozitiv fără grijă la negative: dacă vreunul dintre termeni poate fi negativ, rezultatul % poate ieși negativ — corectează cu (x % m + m) % m.

Recapitulare

Modulo se distribuie peste adunare: (a + b) % m = (a % m + b % m) % m.
Reduci % m după fiecare adunare ca să ții numerele mici și să eviți overflow-ul; rezultatul matematic e neschimbat.
Mai aplici un % m la final pentru că suma a două resturi poate ea însăși depăși m.