Numere mari: introducere

Tipul long long din C++ ajunge până la ~9.2 · 10¹⁸ (aproximativ 19 cifre). Dacă problema cere 100!, 2^200 sau un număr cu 500 de cifre, niciun tip standard nu încape. Trebuie să simulăm aritmetica la mână, cifră cu cifră.

Această lecție pune bazele: cum reprezentăm numere oricât de mari și cum le citim / afișăm. Următoarele lecții vor arăta fiecare operație (adunare, scădere, înmulțire, împărțire) pe rând.

Când ai nevoie de numere mari?

N! pentru N ≥ 25 (25! depășește long long).
a^n pentru a^n > 10¹⁸.
Combinări C(n, k) fără modulo, pentru n mare.
Sume mari de serii.
Probleme care cer numere cu „câteva sute de cifre”.

Când intrarea în enunț e o sumă/produs cu peste 19 cifre, e un semnal clar că ai nevoie de numere mari.

Reprezentarea ca vector de cifre

Convenția clasică la olimpiade: stocăm cifrele în ordine inversă (de la cea mai puțin semnificativă la cea mai semnificativă).

Număr: 12345
Vector: a[1] = 5
        a[2] = 4
        a[3] = 3
        a[4] = 2
        a[5] = 1

La poziția a[0] păstrăm lungimea (numărul de cifre).

De ce în ordine inversă?

Pentru că operațiile aritmetice pornesc de la unități. Când aduni 457 + 89, aduni întâi 7 + 9, apoi 5 + 8, apoi 4 + 0. În reprezentarea inversă, a[1] e direct cifra unităților - nu trebuie să „te întorci” la sfârșitul vectorului.

Dacă ai stoca în ordine normală (cel mai semnificativ la index 1), ai avea două opțiuni la operații:

Parcurgi invers (de la coadă spre cap) - inconfortabil.
Reverse la input și la output - dublă muncă inutilă.

Ordinea inversă elimină ambele bătăi de cap.

Citirea unui număr mare

Numărul vine de obicei ca șir de caractere (pentru că e prea mare pentru int). Îl parcurgem și umplem vectorul:

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

const int NMAX = 1005;
int a[NMAX];
char s[NMAX];

void citire(int v[]) {
    fin >> s;
    int len = strlen(s);
    v[0] = len;
    for (int i = 1; i <= len; i++) {
        v[i] = s[len - i] - '0';
    }
}

Pas cu pas pentru input `12345`

s = "12345" (șirul are len = 5)
v[0] = 5 (lungimea)
i = 1: v[1] = s[4] - '0' = '5' - '0' = 5
i = 2: v[2] = s[3] - '0' = '4' - '0' = 4
i = 3: v[3] = s[2] - '0' = '3' - '0' = 3
i = 4: v[4] = s[1] - '0' = '2' - '0' = 2
i = 5: v[5] = s[0] - '0' = '1' - '0' = 1

Rezultat: v = [5, 5, 4, 3, 2, 1] (unde v[0] = 5 = lungimea).

Afișarea unui număr mare

Parcurgem vectorul în ordine inversă (de la a[a[0]] la a[1]), adică de la cea mai semnificativă cifră la cea mai puțin semnificativă:

void afisare(int v[]) {
    for (int i = v[0]; i >= 1; i--) {
        fout << v[i];
    }
    fout << "\n";
}

Caz special: numărul 0

Reprezentarea lui 0: v[0] = 1, v[1] = 0. Afișează 0 corect.

Nu lăsa niciodată v[0] = 0 (lungime zero) - ar afișa nimic și ar sparge alte operații.

Inițializarea vectorilor

Dacă a, b, c sunt declarate global (în afara lui main), toate elementele sunt automat 0. Asta e exact ce vrem - cifrele „lipsă” dincolo de lungimea reală sunt considerate 0, ceea ce simplifică algoritmii.

const int NMAX = 1005;
int a[NMAX]; // global — toate sunt 0 la start

int main() {
    // ... operații
}

Dacă ai declara local (în main), ar trebui memset(a, 0, sizeof(a)) - riști să uiți și să cad în buguri imprevizibile.

Exemplu complet: citesc și afișez un număr

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

const int NMAX = 1005;
int a[NMAX];
char s[NMAX];

void citire(int v[]) {
    fin >> s;
    int len = strlen(s);
    v[0] = len;
    for (int i = 1; i <= len; i++) {
        v[i] = s[len - i] - '0';
    }
}

void afisare(int v[]) {
    for (int i = v[0]; i >= 1; i--) {
        fout << v[i];
    }
    fout << "\n";
}

int main() {
    citire(a);
    afisare(a);
    return 0;
}

date.in: 123456789012345678901234567890
date.out: 123456789012345678901234567890

Programul citește un număr cu 30 de cifre și îl afișează identic. Atât - lecția actuală arată doar acest „IO” de bază.

Compararea a două numere mari

Pe lângă reprezentare, e util să știm să comparăm două numere mari (ex. înainte de scădere, trebuie să știi care e mai mare). Algoritmul e simplu:

Dacă lungimile diferă, numărul cu mai multe cifre e mai mare.
Dacă sunt egale, comparăm cifrele de la cea mai semnificativă spre cea mai puțin semnificativă. Prima diferență decide.

// Returnează:
//   1 dacă a > b
//   0 dacă a == b
//  -1 dacă a < b
int compara(int a[], int b[]) {
    if (a[0] != b[0]) {
        if (a[0] > b[0]) {
            return 1;
        } else {
            return -1;
        }
    }
    for (int i = a[0]; i >= 1; i--) {
        if (a[i] != b[i]) {
            if (a[i] > b[i]) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    return 0;
}

Atenție: funcționează corect doar dacă numerele sunt stocate fără zero-uri inutile în față. De aceea, după fiecare operație care poate produce zero-uri inutile (mai ales scăderea), trebuie să le eliminăm. Vezi detaliile în lecția de scădere.

Alternative la reprezentarea cu cifre

1. Șir de caractere direct

Poți face operații direct pe char s[]. Mai ușor la citire/afișare, dar fiecare operație cere conversie char ↔︎ int. Mai puțin curat, mai predispus la bug-uri. Nu recomand.

2. Cifre pe „grupe” (baza 10⁹)

În loc să stochezi o cifră zecimală per element (0-9), stochezi un grup de 9 cifre per int (0-999999999). Numărul se „comprimă” de 9 ori.

12345678901234567890 devine:
a[1] = 567890        (grupa unităților, doar 6 cifre)
a[2] = 123456789     (grupa de mijloc)
a[3] = 12            (grupa de top, doar 2 cifre)

De 9 ori mai puține operații pe toată aritmetica. Dar codul e mai complicat - mai ales la afișare (trebuie să pui zerouri în față la grupele intermediare). Folosit la olimpiade când viteza contează.

3. `__int128` (GCC specific)

Tip de 128 de biți, ajunge la ~1.7 · 10³⁸ (cam 38 de cifre). Nu e standard C++, nu se afișează cu cout, dar poate fi suficient pentru cazuri medii.

4. BigInt din librării (Python, Java)

Multe limbaje au BigInt native. C++ nu - trebuie scris de mână sau folosită o librărie externă (GMP, Boost).

În această carte folosim varianta cu cifre zecimale (cea mai simplă didactic). Restul sunt optimizări pentru mai târziu.

Greșeli frecvente

1. Confuzia ordinii cifrelor

Ordinea e inversă: v[1] e cifra unităților, nu cea a sutelor. Dacă scrii v[1] = s[0] - '0', inversezi totul. Mereu: v[i] = s[len - i] - '0'.

2. Afișare în ordine greșită

La afișare parcurgi invers: for (int i = v[0]; i >= 1; i--). Dacă faci for (int i = 1; i <= v[0]; i++), afișezi numărul oglindit.

3. Declararea locală fără inițializare

Vectorii locali conțin gunoi, nu 0. Dacă vrei vectori locali, folosește memset(a, 0, sizeof(a)). Mai simplu: declară-i global.

4. `NMAX` prea mic

Pentru numere cu 1000 de cifre, NMAX = 1005 ajunge pentru citire. Dar operațiile pot crește lungimea: adunarea cu 1, înmulțirea cu lenA + lenB. Dimensionează cu margine.

5. Citire cu `fin >> v[i]`

Nu merge - ar citi un singur int de până la 10 cifre. Mereu citește ca șir de caractere și convertește manual.

Ce să reții

Reprezentarea clasică: a[0] = lungime, a[1..len] = cifrele în ordine inversă (LSB la a[1]).
Citește ca șir de caractere (char s[NMAX]), apoi convertește.
Afișare: parcurgi de la a[0] la 1 (coadă spre cap).
Declară vectorii global - inițializare automată cu 0.
Comparație: lungime prima, apoi cifre de la cel mai semnificativ la cel mai puțin.
Mereu păstrează numerele fără zero-uri inutile în față.
Alternative (grupe de cifre, __int128) sunt optimizări, nu necesitate didactică.