Împărțirea unui număr mare la un număr natural

Ideea: împărțire lungă de la cifra cea mai semnificativă

Reamintim convenția capitolului: un număr mare e un vector<int> cu cifra unităților pe indexul 0 (reprezentare inversată, little-endian), în baza 10. Deci cifra cea mai semnificativă stă pe indexul cel mai mare.

La adunare și scădere porneai de la unități, adică de la indexul 0, fiindcă acolo apare transportul. Împărțirea lungă merge invers: pe hârtie începi din stânga, de la cifra cea mai semnificativă, și cobori spre unități. Motivul este că restul unei cifre superioare influențează cifrele de mai jos, nu invers — informația curge de sus în jos. În reprezentarea noastră inversată, „de sus în jos” înseamnă de la indexul mare spre indexul 0.

Mecanismul e simplu și se sprijină pe un singur „rest curent”:

• pornești cu rest = 0;
• la fiecare cifră (de la cea mai semnificativă): rest = rest * 10 + cifra;
• cifra câtului pentru poziția curentă este rest / d;
• actualizezi rest = rest % d.

La final, rest este chiar restul împărțirii, iar cifrele câtului — adunate în ordinea în care le-ai produs — formează câtul.

Exemplu pas cu pas: 4071 : 7

Numărul 4071 se stochează inversat ca [1, 7, 0, 4] (unitățile pe indexul 0). Parcurgem de la indexul 3 spre 0, deci în ordinea cifrelor 4, 0, 7, 1:

• cifra 4: rest = 0 * 10 + 4 = 4; cifra câtului = 4 / 7 = 0; rest = 4 % 7 = 4;
• cifra 0: rest = 4 * 10 + 0 = 40; cifra câtului = 40 / 7 = 5; rest = 40 % 7 = 5;
• cifra 7: rest = 5 * 10 + 7 = 57; cifra câtului = 57 / 7 = 8; rest = 57 % 7 = 1;
• cifra 1: rest = 1 * 10 + 1 = 11; cifra câtului = 11 / 7 = 1; rest = 11 % 7 = 4.

Cifrele câtului, în ordinea producerii, sunt 0 5 8 1, adică numărul 0581 = 581. Restul final este 4. Verificare: 581 * 7 + 4 = 4067 + 4 = 4071. Corect.

Observă cum primul 0 apare în față (cifra cea mai semnificativă a câtului) și trebuie eliminat ca să obținem forma canonică 581.

Implementare C++

Funcția primește numărul mare inversat și divizorul d, întoarce câtul ca vector inversat și pune restul în parametrul rest. Parcurgem de la indexul mare la 0, construim cifrele câtului tot inversat, apoi tăiem zerourile nesemnificative.

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

// a: numar mare inversat (cifra unitatilor pe indexul 0), baza 10
// d: divizor natural mic (d > 0)
// rest: primeste restul impartirii
// intoarce catul, tot ca vector inversat
vector<int> impartLung(const vector<int>& a, int d, long long& rest) {
    int n = a.size();
    vector<int> cat(n, 0);       // catul are cel mult n cifre
    rest = 0;                    // long long: rest poate ajunge ~ 10 * d

    // parcurgem de la cifra cea mai semnificativa (index mare) spre 0
    for (int i = n - 1; i >= 0; i--) {
        rest = rest * 10 + a[i];     // coboram cifra langa rest
        cat[i] = (int)(rest / d);    // cifra catului pe aceeasi pozitie
        rest = rest % d;             // ce ramane trece la cifra urmatoare
    }

    // eliminam zerourile nesemnificative din fata (indicii mari ai catului)
    while (cat.size() > 1 && cat.back() == 0) {
        cat.pop_back();
    }
    return cat;
}

int main() {
    // 4071 stocat inversat: unitatile pe indexul 0
    vector<int> a = {1, 7, 0, 4};
    int d = 7;
    long long rest;

    vector<int> cat = impartLung(a, d, rest);

    // afisam catul de la cifra cea mai semnificativa la unitati
    for (int i = cat.size() - 1; i >= 0; i--) {
        cout << cat[i];          // cat 581
    }
    cout << " rest " << rest << "\n";   // cat 581 rest 4
    return 0;
}

Punem cifra câtului tot pe indexul i, deci câtul iese stocat inversat, la fel ca intrarea — consistent cu restul capitolului. La afișare îl parcurgem invers.

Complexitate

Aici n este numărul de cifre al numărului mare. Facem o singură trecere, cu operații O(1) pe cifră, deci algoritmul este liniar.

Recapitulare

• Împărțirea lungă a unui număr mare parcurge cifrele de la indexul mare spre 0, invers față de adunare și scădere.
• La fiecare pas: rest = rest * 10 + cifra, cifra câtului = rest / d, apoi rest = rest % d; la final rest este restul împărțirii.
• Elimini zerourile nesemnificative din față ale câtului și verifici că d > 0 înainte de a împărți.