Numere mari: împărțirea cu rest la un număr natural

Împărțirea unui număr mare A la un număr natural „mic” (care încape în int sau long long) funcționează ca împărțirea lungă de la școală: mergem de la cifra cea mai semnificativă spre cea mai puțin semnificativă, acumulând restul la fiecare pas.

Spre deosebire de celelalte operații (care pornesc de la cifra unităților), împărțirea pornește de la stânga.

Algoritm

Facem împărțirea ca la școala primară. La fiecare pas avem un rest curent. Aducem „jos” cifra următoare (adică lipim cifra la rest), împărțim, cifra cât merge să împărțim e cifra rezultatului la acea poziție, noul rest e restul efectiv al împărțirii.

rest = 0
pentru i = lenA .. 1:   // de la cea mai semnificativă la cea mai puțin
    rest = rest * 10 + a[i]
    c[i] = rest / x
    rest = rest % x
c[0] = lenA
// elimin zero-urile din față la c

La final, rest conține restul împărțirii (cât a rămas nedivizibil).

Pas cu pas: `1234 / 7`

Împărțire lungă:

1234 / 7:
  12 / 7 = 1 rest 5  →  c[4] = 1, rest = 5
  53 / 7 = 7 rest 4  →  c[3] = 7, rest = 4
  44 / 7 = 6 rest 2  →  c[2] = 6, rest = 2

Aici am început de la cifra „1234” (prima cifră din stânga) - dar reprezentarea noastră e inversă. Deci parcurgem a[4]=1, a[3]=2, a[2]=3, a[1]=4 în această ordine.

Reprezentare:

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

Algoritm (parcurgere i = 4, 3, 2, 1):

i	a[i]	rest vechi	rest·10 + a[i]	c[i] = ÷7	rest nou
4	1	0	1	0	1
3	2	1	12	1	5
2	3	5	53	7	4
1	4	4	44	6	2

Rezultat brut: c[0]=4, c[1]=6, c[2]=7, c[3]=1, c[4]=0.

Cifra de top (c[4] = 0) e zero. Elimin prin:

while (c[0] > 1 && c[c[0]] == 0) c[0]--;

c[0] devine 3. Rezultat: cifrele c[1]=6, c[2]=7, c[3]=1 → afișat în ordine inversă → 176.

Verificare: 1234 = 7 · 176 + 2 = 1232 + 2 = 1234 ✓. Rest final = 2.

Cod

const int NMAX = 1005;
int a[NMAX], c[NMAX];

// Împarte A la x. Scrie câtul în c, returnează restul.
long long impartireLaNatural(int a[], long long x, int c[]) {
    long long rest = 0;
    int len = a[0];
    for (int i = len; i >= 1; i--) {
        rest = rest * 10 + a[i];
        c[i] = rest / x;
        rest = rest % x;
    }
    c[0] = len;
    // elimin zero-urile din față
    while (c[0] > 1 && c[c[0]] == 0) {
        c[0] = c[0] - 1;
    }
    return rest;
}

Complexitate: O(lenA). Fiecare cifră e procesată o singură dată.

Atenție la long long: rest * 10 + a[i] - dacă x ≤ 10⁹, atunci rest < x ≤ 10⁹ și rest * 10 < 10¹⁰ - depășește int, dar încape în long long. Folosește long long pentru siguranță.

Exemplu complet: citesc A și x, afișez câtul și restul

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

const int NMAX = 1005;
int a[NMAX], c[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";
}

long long impartireLaNatural(int a[], long long x, int c[]) {
    long long rest = 0;
    int len = a[0];
    for (int i = len; i >= 1; i--) {
        rest = rest * 10 + a[i];
        c[i] = rest / x;
        rest = rest % x;
    }
    c[0] = len;
    while (c[0] > 1 && c[c[0]] == 0) {
        c[0] = c[0] - 1;
    }
    return rest;
}

int main() {
    long long x;
    citire(a);
    fin >> x;
    long long rest = impartireLaNatural(a, x, c);
    afisare(c);
    fout << rest;
    return 0;
}

date.in:

1234
7

date.out:

176
2

Aplicație 1: verificarea divizibilității

Numărul A (cu 500 cifre) e divizibil cu x?

Răspuns: da ⇔ restul împărțirii e 0.

long long rest = impartireLaNatural(a, x, c);
if (rest == 0) {
    fout << "DA";
} else {
    fout << "NU";
}

Alternativă mai rapidă (dacă nu vrei câtul): calculezi doar restul, nu stochezi și câtul:

long long restModulo(int a[], long long x) {
    long long rest = 0;
    for (int i = a[0]; i >= 1; i--) {
        rest = (rest * 10 + a[i]) % x;
    }
    return rest;
}

Mai compact, cu un singur pas de calcul per cifră. Foarte util pentru „calculează A mod x” când A e număr mare.

Aplicație 2: `A mod x` fără a stoca câtul

Problema: „dă-mi A mod 10^9+7” unde A e un număr cu 1000 de cifre.

const long long MOD = 1000000007LL;
long long restModulo(int a[], long long x) {
    long long rest = 0;
    for (int i = a[0]; i >= 1; i--) {
        rest = (rest * 10 + a[i]) % x;
    }
    return rest;
}
// ...
fout << restModulo(a, MOD);

Acum rest-ul încape mereu în long long și ieși cu rezultat corect modulo prim.

Aplicație 3: împărțire la 10 = „scoate ultima cifră”

Scoate cifra unităților dintr-un număr mare.

Împărțire la 10: câtul e numărul fără ultima cifră, restul e cifra scoasă. Împărțirea noastră funcționează. Dar există o variantă mai rapidă - shift:

// a = a / 10 (fără rest)
void shiftDreapta(int a[]) {
    for (int i = 1; i < a[0]; i++) {
        a[i] = a[i + 1];
    }
    a[a[0]] = 0;
    if (a[0] > 1) {
        a[0] = a[0] - 1;
    }
}

Complexitate O(lenA), la fel. Dar evită calculul de împărțire propriu-zis - operație foarte rapidă.

Aplicație 4: conversie zecimală → altă bază

Convertește un număr mare din baza 10 în baza B.

Ideea: repetat, împart la B și restul e următoarea cifră în baza B (începând cu cea mai puțin semnificativă):

int a[NMAX], cat[NMAX];
int cifreBaza[NMAX]; // cifrele în baza B
int nr = 0;

while (a[0] > 1 || a[1] > 0) { // cât timp a > 0
    long long rest = impartireLaNatural(a, B, cat);
    nr = nr + 1;
    cifreBaza[nr] = rest;
    // copiez cat înapoi în a
    for (int i = 0; i <= cat[0]; i++) {
        a[i] = cat[i];
    }
}

// afișez invers
for (int i = nr; i >= 1; i--) {
    fout << cifreBaza[i];
}

Acesta e modul clasic de a converti un număr mare din baza 10 în orice altă bază. Vezi lecția de sisteme de numerație pentru detalii.

Greșeli frecvente

1. Parcurgere în ordine greșită

Împărțirea pornește de la cifra cea mai semnificativă (deci de la i = a[0] descrescător). Dacă parcurgi i = 1 la a[0], obții un rezultat complet greșit.

2. Nu elimini zero-urile din față la cât

Dacă 1234 / 7 = 176 dar reprezentezi ca 0176, afișarea iese greșit sau comparațiile ulterioare sunt confuze. Mereu:

while (c[0] > 1 && c[c[0]] == 0) c[0]--;

3. Overflow la `rest * 10`

Dacă x ≤ 10⁹ și rest < x, atunci rest * 10 + a[i] ≤ 10¹⁰ - depășește int. Folosește long long pentru rest.

4. Împărțire la 0

x = 0 → diviziune prin zero → program crapă. Verifică în cod dacă e cazul:

if (x == 0) {
    fout << "diviziune prin zero";
    return 0;
}

5. Rezultatul câtului e `0`

Dacă A < x, câtul e 0 și restul e chiar A. Codul nostru gestionează corect:

c[0] = lenA la început
Toate c[i] sunt 0 după împărțire
Bucla de eliminare zero-uri coboară c[0] la 1 (păstrăm lungimea minimă de 1)
Afișează 0

Ce să reții

Împărțire lungă: pornești de la cifra cea mai semnificativă (i = a[0] descrescător).
Pas: rest = rest * 10 + a[i]; c[i] = rest / x; rest = rest % x;
Returnezi restul final.
Elimină zero-urile din față la cât, cu while (c[0] > 1 && c[c[0]] == 0) c[0]--.
Complexitate: O(lenA).
Pentru „doar mod x”, poți omite stocarea câtului - mai rapid și mai simplu.
Aplicații: divizibilitate, modulo numere mari, conversie în altă bază.
Folosește long long pentru rest - depășește int ușor.

Cu această lecție, ai toate operațiile de bază pe numere mari: adunare, scădere, înmulțire cu natural, împărțire cu rest la natural. Înmulțirea a două numere mari e o operație avansată (algoritmi O(L²) naiv, O(L log L) cu FFT) - la olimpiade de liceu nu e cerută direct decât la Lot.