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
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)
- Capitol
- Numere mari
Exemple
Intrare
123456789012345678901234567890 9
Ieșire așteptată
1111111101111111110111111111010
Intrare
99999999999 1000000000
Ieșire așteptată
99999999999000000000
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.
/*
* 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.