Okorosso

Умножение длинных

May 13th, 2021
550
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <cstdio>
  5. #include <string>
  6. #include <vector>
  7.  
  8. typedef std::vector<int> lnum;
  9. const int base = 1000 * 1000 * 1000;
  10.  
  11. void print(lnum a) {
  12.     bool flag = false;
  13.     FILE *fout = fopen("output.txt", "a");
  14. //    fprintf(fout, "\n");
  15.     for (int i = a.size() - 1; i >= 0; i--)
  16.         if ((a[i] != 0) || (a[i] == 0 && flag == 1)) {
  17.             if (flag == 0) {
  18.                 flag = true;
  19.                 fprintf(fout, "%d", a[i]);
  20.             } else
  21.                 fprintf(fout, "%09d", a[i]);
  22.         }
  23.  
  24. }
  25.  
  26. lnum toVec(std::string &str) {
  27.     lnum toReturn;
  28.     for (int i = (int) str.length(); i > 0; i -= 9)
  29.         if (i < 9)
  30.             toReturn.push_back(atoi(str.substr(0, i).c_str()));
  31.         else
  32.             toReturn.push_back(atoi(str.substr(i - 9, 9).c_str()));
  33.     return toReturn;
  34. }
  35.  
  36. void multiply(lnum a, lnum b) {
  37.     lnum c(a.size() + b.size());
  38.     for (size_t i = 0; i < a.size(); ++i)
  39.         for (int j = 0, carry = 0; j < (int) b.size() || carry; ++j) {
  40.             long long cur = c[i + j] + a[i] * 1ll * (j < (int) b.size() ? b[j] : 0) + carry;
  41.             c[i + j] = int(cur % base);
  42.             carry = int(cur / base);
  43.         }
  44.     while (c.size() > 1 && c.back() == 0)
  45.         c.pop_back();
  46.     print(c);
  47. }
  48.  
  49. int main() {
  50.     using namespace std;
  51.     ifstream cin("input.txt");
  52.     ofstream cout("output.txt");
  53.     string first, second;
  54.     lnum firstLnum, secondLnum;
  55.     long long b;
  56.     cin >> first >> second >> b;
  57.  
  58.     firstLnum = toVec(first);
  59.     secondLnum = toVec(second);
  60.     multiply(firstLnum, secondLnum);
  61.  
  62.  
  63.     return 0;
  64. }
RAW Paste Data