fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef complex<double> ftype;
  6. const double pi = acos(-1);
  7. const int maxn = 1 << 17;
  8. ftype w[maxn];
  9.  
  10. void init() {
  11.     for(int i = 0; i < maxn; i++) {
  12.         w[i] = polar(1., 2 * pi / maxn * i);
  13.     }
  14. }
  15.  
  16. template<typename T>
  17. void fft(T *in, ftype *out, int n, int k = 1) {
  18.     if(n == 1) {
  19.         *out = *in;
  20.         return;
  21.     }
  22.     int t = maxn / n;
  23.     n >>= 1;
  24.     fft(in, out, n, 2 * k);
  25.     fft(in + k, out + n, n, 2 * k);
  26.     for(int i = 0, j = 0; i < n; i++, j += t) {
  27.         ftype t = w[j] * out[i + n];
  28.         out[i + n] = out[i] - t;
  29.         out[i] += t;
  30.     }
  31. }
  32.  
  33. vector<ftype> evaluate(vector<int> p) {
  34.     while(__builtin_popcount(p.size()) != 1) {
  35.         p.push_back(0);
  36.     }
  37.     vector<ftype> res(p.size());
  38.     fft(p.data(), res.data(), p.size());
  39.     return res;
  40. }
  41.  
  42. vector<int> interpolate(vector<ftype> p) {
  43.     int n = p.size();
  44.     vector<ftype> inv(n);
  45.     fft(p.data(), inv.data(), n);
  46.     vector<int> res(n);
  47.     for(int i = 0; i < n; i++) {
  48.         res[i] = round(real(inv[i]) / n);
  49.     }
  50.     reverse(begin(res) + 1, end(res));
  51.     return res;
  52. }
  53.  
  54. void align(vector<int> &a, vector<int> &b) {
  55.     int n = a.size() + b.size() - 1;
  56.     while(a.size() < n) {
  57.         a.push_back(0);
  58.     }
  59.     while(b.size() < n) {
  60.         b.push_back(0);
  61.     }
  62. }
  63.  
  64. vector<int> poly_multiply(vector<int> a, vector<int> b) {
  65.     align(a, b);
  66.     auto A = evaluate(a);
  67.     auto B = evaluate(b);
  68.     for(int i = 0; i < A.size(); i++) {
  69.         A[i] *= B[i];
  70.     }
  71.     return interpolate(A);
  72. }
  73.  
  74. const int base = 10;
  75. vector<int> normalize(vector<int> c) {
  76.     int carry = 0;
  77.     for(auto &it: c) {
  78.         it += carry;
  79.         carry = it / base;
  80.         it %= base;
  81.     }
  82.     while(carry) {
  83.         c.push_back(carry % base);
  84.         carry /= base;
  85.     }
  86.     return c;
  87. }
  88.  
  89. vector<int> multiply(vector<int> a, vector<int> b) {
  90.     return normalize(poly_multiply(a, b));
  91. }
  92.  
  93. signed main() {
  94.     ios::sync_with_stdio(0);
  95.     cin.tie(0);
  96.     init();
  97.     for(int a = 1; a <= 1000; a++) {
  98.         for(int b = 1; b <= a; b++) {
  99.             vector<int> A{a}, B{b};
  100.             auto C = multiply(normalize(A), normalize(B));
  101.             while(C.back() == 0) {
  102.                 C.pop_back();
  103.             }
  104.             assert(C == normalize({a * b}));
  105.         }
  106.     }
  107. }
  108.  
Success #stdin #stdout 0.53s 17296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/whaSln
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!