Numere mari: înmulțirea cu un număr natural

Înmulțirea unui număr mare A cu un număr „normal” x (care încape în int sau long long) e mult mai simplă decât înmulțirea a două numere mari. Apare frecvent: calcul de factorial, puteri, sume aritmetice cu produse.

Algoritm

Ca la școala primară: înmulțim fiecare cifră din A cu întregul x, adunăm transport-ul precedent, extragem cifra de unități, propagăm transport-ul.

Diferența față de adunare: transport-ul poate fi mai mare decât 1 (pentru că cifră · x poate fi un număr de 2-3 cifre).

transport = 0
pentru i = 1 .. lenA:
    produs = a[i] * x + transport
    c[i] = produs % 10
    transport = produs / 10
cât timp transport > 0:
    lenA = lenA + 1
    c[lenA] = transport % 10
    transport = transport / 10

Pas cu pas: 1234 · 6 = 7404

• a = 1234 → a[0]=4, a[1]=4, a[2]=3, a[3]=2, a[4]=1
• x = 6

Transport final = 0. Rezultat: c[0]=4, c[1]=4, c[2]=0, c[3]=4, c[4]=7 → 7404 ✓.

Pas cu pas: 999 · 12345 = 12332655 (transport mare)

• a = 999 → a[0]=3, a[1]=9, a[2]=9, a[3]=9
• x = 12345

După bucla principală, transport = 12332. Adăugăm cifrele lui 12332 pe rând:

Rezultat: cifrele 5, 5, 6, 2, 3, 3, 2, 1 → citite invers → 12332655 ✓.

Cod

const int NMAX = 2005; // cresc față de adunare/scădere: produsul se poate dubla

void inmultireCuNatural(int a[], long long x, int c[]) {
    int len = a[0];
    long long transport = 0;
    for (int i = 1; i <= len; i++) {
        long long produs = (long long)a[i] * x + transport;
        c[i] = produs % 10;
        transport = produs / 10;
    }
    while (transport > 0) {
        len = len + 1;
        c[len] = transport % 10;
        transport = transport / 10;
    }
    c[0] = len;
}

Complexitate: O(lenA + log x). Bucla principală e O(lenA), apoi bucla de „descărcare” a transport-ului adaugă cel mult log₁₀(x) cifre noi.

Atenție la tipul long long: a[i] * x poate depăși int dacă x e mare (ex. a[i] = 9, x = 10⁹ → produs 9 · 10⁹ depășește int). Folosește long long pentru produs și transport.

Aplicație: factorialul unui număr

N! crește exploziv: 20! are 19 cifre (încape în long long), dar 25! are 26 de cifre (nu mai încape). Pentru N = 100, N! are 158 cifre.

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

const int NMAX = 2005;
int fact[NMAX];

void inmultireCuNatural(int a[], long long x, int c[]) {
    int len = a[0];
    long long transport = 0;
    for (int i = 1; i <= len; i++) {
        long long produs = (long long)a[i] * x + transport;
        c[i] = produs % 10;
        transport = produs / 10;
    }
    while (transport > 0) {
        len = len + 1;
        c[len] = transport % 10;
        transport = transport / 10;
    }
    c[0] = len;
}

int main() {
    int N;
    fin >> N;

    fact[0] = 1;
    fact[1] = 1; // fact = 1

    for (int k = 2; k <= N; k++) {
        inmultireCuNatural(fact, k, fact); // fact = fact * k
    }

    for (int i = fact[0]; i >= 1; i--) {
        fout << fact[i];
    }
    return 0;
}

date.in: 100
date.out: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Atenție: fact e și intrare și ieșire pentru inmultireCuNatural. Funcția noastră scrie c[i] după ce citește a[i], deci acest alias-ing e sigur.

Aplicație: a^n (ridicarea la putere)

Prin înmulțiri succesive:

int rez[NMAX];

void putere(long long a, int n, int rez[]) {
    rez[0] = 1;
    rez[1] = 1; // rez = 1

    for (int k = 1; k <= n; k++) {
        inmultireCuNatural(rez, a, rez); // rez = rez * a
    }
}

Complexitate: O(n · lenRez). Pentru n = 100, a = 2: 2^100 are 31 cifre, deci complexitate ~100 · 31 = 3100 operații. Foarte rapid.

Optimizare (mai avansată): exponențiere rapidă cu log n înmulțiri în loc de n. Dar atunci trebuie și înmulțirea a două numere mari, care e subiect avansat.

Aplicație: sume cu factorial

Calculează 1! + 2! + 3! + ... + N! pentru N ≤ 100.

int suma[NMAX], fact[NMAX];

// inițial suma = 0, fact = 1
fact[0] = 1;
fact[1] = 1;
suma[0] = 1;
suma[1] = 0;

for (int k = 1; k <= N; k++) {
    inmultireCuNatural(fact, k, fact); // fact = k!
    adunare(suma, fact, suma);          // suma = suma + k!
}
afisare(suma);

Folosește adunare din lecția anterioară.

Variantă: x poate fi foarte mare (ex. 10⁹)

Codul de mai sus merge cu x până la ~10¹⁸ (limita long long), atâta timp cât (long long)a[i] * x + transport nu depășește. Pentru a[i] ≤ 9 și transport ≤ 10¹⁸, avem 9 · 10¹⁸ ≈ 10¹⁹ - depășește long long.

În practică, pentru x ≤ 10⁹: - a[i] * x ≤ 9 · 10⁹ - transport ≤ 10⁹ (cam de ordinul lui x) - produs ≤ 9 · 10⁹ + 10⁹ = 10¹⁰ - OK, încape în long long.

Pentru x și mai mare, folosește reprezentare pe grupuri de cifre (vezi nota din lecția de reprezentare) sau un alt algoritm.

Greșeli frecvente

1. Uitarea buclei finale de descărcare a transport-ului

După bucla principală, transport-ul poate fi încă nenul și mare. Mereu:

while (transport > 0) {
    len = len + 1;
    c[len] = transport % 10;
    transport = transport / 10;
}

Dacă faci doar un if în loc de while, ratezi cifrele de top când transport-ul are mai multe cifre.

2. Overflow la produs

(long long)a[i] * x + transport - dacă a[i] și x sunt amândouă int și produsul depășește int, ieși cu valoare greșită înainte să-l salvezi în long long. Forțează cast cu (long long) la un operand.

3. Nu inițializezi fact sau rez

Fără rez[0] = 1; rez[1] = 1; (adică rez = 1), pornești de la 0. Orice înmulțire cu 0 dă 0.

4. NMAX prea mic

Pentru 100! (158 cifre), NMAX = 200 ajunge. Dar pentru 1000! (2568 cifre), ai nevoie de NMAX = 3000. Mereu dimensionează cu o marjă.

5. Uitarea că c și a pot fi același vector

Codul funcționează corect în acest caz (scrii c[i] după ce ai citit a[i]), dar verifică când ai dubii. Scrierea peste a în timpul iterării ar fi un bug greu de găsit.

Ce să reții

• Înmulțire cu natural = parcurgere cifrică + transport mare (poate fi mai mult decât 1).
• Formula: produs = a[i] * x + transport; c[i] = produs % 10; transport = produs / 10.
• După bucla principală, descarcă transport-ul cu un while (poate avea multe cifre).
• Folosește long long pentru produs și transport - int depășește ușor.
• Complexitate: O(lenA + log x).
• Aplicații principale: N!, a^n, sume cu produse.
• Pentru x > 10⁹, atenție la overflow - consideră reprezentare pe grupuri de cifre.