SHARE
TWEET

Untitled

a guest Sep 22nd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void multiply(vector < uint > a, vector < uint > b, vector < uint > &res) {
  2.     if (a.size() == 1) {
  3.         res = b;
  4.         fori(b.size()) res[i] *= a[0];
  5.         return ;
  6.     }
  7.     if (b.size() == 1) {
  8.         res = a;
  9.         fori(a.size()) res[i] *= b[0];
  10.         return ;
  11.     }
  12.     if (a.size() + b.size() <= 10) {
  13.         res.resize(a.size() + b.size() - 1);
  14.         for (int i = 0; i < a.size(); i++) {
  15.             for (int j = 0; j < b.size(); j++) {
  16.                 res[i + j] += (a[i] * b[j]);
  17.             }
  18.         }
  19.         return ;
  20.     }
  21.     int cnt1 = a.size(), cnt2 = b.size();
  22.     if (a.size() > b.size()) {
  23.         while (a.size() != b.size()) b.pb(0);
  24.     } else if (a.size() < b.size()) {
  25.         while (a.size() != b.size()) a.pb(0);
  26.     }
  27.     if (a.size() != b.size()) {
  28.         //cout << cnt1 << " " << cnt2 << "\n";
  29.         //cout << a.size() << " " << b.size() << "\n";
  30.         while (true) {}
  31.         exit(0);
  32.     }
  33.     int m = (a.size() + 1) / 2;
  34.     vector < uint > a0, a1, b0, b1;
  35.     vector < uint > a0b0, a1b1;
  36.     a0.resize(m);
  37.     b0.resize(m);
  38.     a1.resize(a.size() - m);
  39.     b1.resize(b.size() - m);
  40.     for (int i = 0; i < m; i++) a0[i] = a[i];
  41.     for (int i = m; i < a.size(); i++) a1[i - m] = a[i];
  42.  
  43.     for (int i = 0; i < m; i++) b0[i] = b[i];
  44.     for (int i = m; i < b.size(); i++) b1[i - m] = b[i];
  45.     multiply(a0, b0, a0b0);
  46.     multiply(a1, b1, a1b1);
  47.     sum(a0, a1);
  48.     sum(b0, b1);
  49.     vector < uint > keks1;
  50.     multiply(a0, b0, keks1);
  51.     //for (auto c: keks1) cout << c << " ";
  52.     //cout << "\n";
  53.     substraction(keks1, a0b0);
  54.     substraction(keks1, a1b1);
  55.     res.resize(a.size() + b.size() - 1);
  56.     for (int i = 0; i < a0b0.size(); i++) {
  57.         res[i] += a0b0[i];
  58.     }
  59.     for (int i = m; i - m < keks1.size(); i++) {
  60.         res[i] += keks1[i - m];
  61.     }
  62.     for (int i = 2 * m; i - 2 * m < a1b1.size(); i++) {
  63.         res[i] += a1b1[i - 2 * m];
  64.     }
  65.     while (true) {
  66.         if (res.back() == 0) res.pop_back();
  67.         else break;
  68.     }
  69.     return ;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top