Înmulțirea unui număr mare cu un număr natural

De ce contează?

Gândește-te cum înmulțeai pe hârtie un număr lung cu un singur număr, de exemplu 4071 × 25. Treceai prin cifre de la dreapta la stânga, înmulțeai fiecare cifră cu 25 și „țineai minte” ce se revărsa peste. Diferența față de adunare: la adunare țineai minte cel mult 1, aici poți ține minte un număr întreg de mai multe cifre.

Ideea: înmulțire ca pe hârtie, dar cu transport mare

Reamintim convenția capitolului: un număr mare e un vector<int> în care cifra unităților stă pe indexul 0 (reprezentare inversată, little-endian), baza 10. Astfel numărul 4071 se scrie [1, 7, 0, 4].

Pentru a-l înmulți cu un factor natural f, parcurgem cifrele de la indexul 0 spre dreapta. Pentru fiecare poziție calculăm:

produs = cifra * f + carry
cifra nouă de pe poziție = produs % 10
transportul către poziția următoare = produs / 10

Esența: la adunare carry-ul era doar 0 sau 1. Aici, fiindcă înmulțim, produs poate fi mare, deci carry-ul poate avea mai multe cifre. Și mai important: după ce am terminat cifrele, transportul rămas trebuie golit cifră cu cifră, pentru că poate adăuga mai multe poziții noi la rezultat.

Exemplu pas cu pas: 4071 × 25

Numărul mare e [1, 7, 0, 4] (cifra unităților prima). Factor f = 25, carry = 0 la început.

poziția 0: produs = 1 * 25 + 0 = 25 → cifra = 25 % 10 = 5, carry = 25 / 10 = 2
poziția 1: produs = 7 * 25 + 2 = 177 → cifra = 177 % 10 = 7, carry = 177 / 10 = 17
poziția 2: produs = 0 * 25 + 17 = 17 → cifra = 17 % 10 = 7, carry = 17 / 10 = 1
poziția 3: produs = 4 * 25 + 1 = 101 → cifra = 101 % 10 = 1, carry = 101 / 10 = 10

Am terminat cifrele, dar carry-ul e 10 (două cifre). Îl golim în buclă:

carry = 10 → adăugăm cifra 10 % 10 = 0, carry devine 10 / 10 = 1
carry = 1 → adăugăm cifra 1 % 10 = 1, carry devine 1 / 10 = 0

Rezultatul inversat e [5, 7, 7, 1, 0, 1], adică citit normal 101775. Observă că un singur carry final (10) a adăugat două cifre noi — exact de aceea golim într-o buclă, nu printr-o singură adăugare.

rez	5	7	7	1	0	1
	0	1	2	3	4	5
	unitati					cel

Rezultatul 4071 × 25 stocat inversat: [5, 7, 7, 1, 0, 1] = 101775. Carry-ul final 10 a produs ultimele doua cifre.

Implementare C++

#include <iostream>
#include <vector>
using namespace std;

// inmulteste numarul mare (inversat, unitatile pe index 0) cu factorul f
vector<int> inmultire(const vector<int>& nr, int f) {
    // cazul special: inmultire cu 0 -> rezultatul este numarul 0
    if (f == 0) {
        return {0};
    }

    vector<int> rez;
    long long carry = 0;                    // long long ca sa evitam overflow

    // parcurgem cifrele de la unitati spre stanga
    for (int i = 0; i < (int)nr.size(); i++) {
        long long produs = (long long)nr[i] * f + carry;
        rez.push_back((int)(produs % 10)); // cifra de pe pozitia curenta
        carry = produs / 10;               // transportul, poate avea mai multe cifre
    }

    // golim tot carry-ul ramas: poate adauga mai multe pozitii noi
    while (carry > 0) {
        rez.push_back((int)(carry % 10));
        carry = carry / 10;
    }

    return rez;
}

int main() {
    // 4071 stocat inversat: unitatile pe index 0
    vector<int> nr = {1, 7, 0, 4};
    int f = 25;

    vector<int> rez = inmultire(nr, f);

    // afisam de la cea mai semnificativa cifra spre unitati
    for (int i = (int)rez.size() - 1; i >= 0; i--) {
        cout << rez[i];
    }
    cout << "\n";                           // 101775

    return 0;
}

Complexitate

Fie n numărul de cifre al numărului mare.

Operație	Timp	De ce
parcurgerea cifrelor	O(n)	atingem fiecare cifră o dată
golirea carry-ului final	O(1) amortizat	carry-ul are cel mult câteva cifre
total	O(n)	factorul nu schimbă ordinul, doar costul constant

Observația-cheie

Marea diferență față de adunarea numerelor mari: acolo carry-ul era mereu 0 sau 1, fiindcă suma a două cifre plus 1 e cel mult 19. Aici înmulțim cu un factor oarecare, deci produs poate fi mare, iar carry-ul produs / 10 poate avea mai multe cifre. De aceea golirea finală trebuie făcută într-o buclă, nu o dată.

Greșeli frecvente

Presupui carry doar 0 sau 1 ca la adunare. La înmulțire carry-ul poate fi un număr de mai multe cifre; folosește produs % 10 și produs / 10, nu scădere fixă.
Uiți să golești carry-ul final într-o buclă while (carry > 0). O singură adăugare la final pierde cifre când carry-ul are două sau mai multe cifre.
Overflow fără long long: cu factor mare, cifra * f + carry poate depăși limita unui int (~2.1 miliarde). Ține produsul în long long.
Uiți cazul factor 0: rezultatul trebuie să fie numărul 0 ({0}), altfel rămâi cu un vector gol sau cu zerouri nedorite în față.

Recapitulare

Parcurgi cifrele inversate; pe fiecare poziție produs = cifra * f + carry, cifra = produs % 10, carry = produs / 10.
Carry-ul poate avea mai multe cifre (spre deosebire de adunare), deci îl golești la final într-o buclă while (carry > 0), adăugând cifre noi.
Folosește long long pentru produs ca să eviți overflow-ul când factorul e mare, și tratează separat factorul 0.