Clasa a XII-a · Numere mariRead in English

Înmulțirea unui număr mare cu un număr mic în C++

În engleză: Multiplying a big number by a small number

O(n)C++1778 de linii3 exemple

Ideea

Numărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie despărțit în cifre. Pentru fiecare cifră a[i], de la unități, calculăm t = a[i] * k + transport (în long long, ca să nu depășim); cifra rezultatului este t % 10, iar transportul devine t / 10. Transportul rămas la final poate avea mai multe cifre, așa că îl descompunem cifră cu cifră. Dacă k = 0, rezultatul este 0.

Descrierea în engleză

The small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t = a[i] * k + carry (in long long, so we do not overflow); the result digit is t % 10, and the carry becomes t / 10. The carry left at the end may have several digits, so we break it down digit by digit. If k = 0, the result is 0.

Complexitate
O(k1 + c), unde k1 este numărul de cifre al numărului mare și c numărul de cifre al lui k
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare

123456789012345678901234567890 9

Ieșire așteptată

1111111101111111110111111111010
Exemplul 2

Intrare

99999999999 1000000000

Ieșire așteptată

99999999999000000000
Exemplul 3

Intrare

123456789 0

Ieșire așteptată

0

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

inmultirea-cu-un-numar-mic.cpp
/*
 * Titlu: Înmulțirea unui număr mare cu un număr mic
 * Clasa: 12
 * Capitol: Numere mari
 * Descriere: Numărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie
 *            despărțit în cifre. Pentru fiecare cifră a[i], de la unități,
 *            calculăm t = a[i] * k + transport (în long long, ca să nu depășim);
 *            cifra rezultatului este t % 10, iar transportul devine t / 10.
 *            Transportul rămas la final poate avea mai multe cifre, așa că îl
 *            descompunem cifră cu cifră. Dacă k = 0, rezultatul este 0.
 * Complexitate: O(k1 + c), unde k1 este numărul de cifre al numărului mare și c
 *               numărul de cifre al lui k
 *
 * Exemplu
 * Intrare: 123456789012345678901234567890 9
 * Ieșire: 1111111101111111110111111111010
 *
 * Exemplu
 * Intrare: 99999999999 1000000000
 * Ieșire: 99999999999000000000
 *
 * Exemplu
 * Intrare: 123456789 0
 * Ieșire: 0
 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> citesteNumar(const string &s)
{
    vector<int> a;
    for (int i = (int)s.size() - 1; i >= 0; i--)
        a.push_back(s[i] - '0');
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}

void afiseazaNumar(const vector<int> &a)
{
    for (int i = (int)a.size() - 1; i >= 0; i--)
        cout << a[i];
    cout << '\n';
}

vector<int> inmultesteMic(const vector<int> &a, long long k)
{
    if (k == 0)
        return vector<int>(1, 0);
    vector<int> c;
    long long transport = 0;
    for (int i = 0; i < (int)a.size(); i++)
    {
        long long t = a[i] * k + transport;
        c.push_back(t % 10);
        transport = t / 10;
    }
    while (transport > 0)
    {
        c.push_back(transport % 10);
        transport /= 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

int main()
{
    string s;
    long long k;
    cin >> s >> k;
    afiseazaNumar(inmultesteMic(citesteNumar(s), k));
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.