ProgMe

Untitled

Oct 22nd, 2023
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. //#define getchar getchar_unlocked
  4.  
  5. using namespace std;
  6.  
  7. typedef complex<double> base;
  8.  
  9. void fft (vector<base> & a, bool invert) {
  10. int n = (int) a.size();
  11. if (n == 1) return;
  12.  
  13. vector<base> a0 (n/2), a1 (n/2);
  14. for (int i=0, j=0; i<n; i+=2, ++j) {
  15. a0[j] = a[i];
  16. a1[j] = a[i+1];
  17. }
  18. fft (a0, invert);
  19. fft (a1, invert);
  20.  
  21. double ang = 2*acos(-1)/n * (invert ? -1 : 1);
  22. base w (1), wn (cos(ang), sin(ang));
  23. for (int i=0; i<n/2; ++i) {
  24. a[i] = a0[i] + w * a1[i];
  25. a[i+n/2] = a0[i] - w * a1[i];
  26. if (invert)
  27. a[i] /= 2, a[i+n/2] /= 2;
  28. w *= wn;
  29. }
  30. }
  31.  
  32. void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {
  33. vector<base> fa (a.begin(), a.end());
  34. vector<base> fb (b.begin(), b.end());
  35. size_t n = 1;
  36. while (n < max (a.size(), b.size())) n <<= 1;
  37. n <<= 1;
  38. fa.resize (n), fb.resize (n);
  39.  
  40. fft (fa, false), fft (fb, false);
  41. for (size_t i=0; i<n; ++i)
  42. fa[i] *= fb[i];
  43. fft (fa, true);
  44.  
  45. res.resize (n);
  46. for (size_t i=0; i<n; ++i)
  47. res[i] = int (fa[i].real() + 0.5);
  48. int carry = 0;
  49. for (size_t i=0; i<n; ++i) {
  50. res[i] += carry;
  51. carry = res[i] / 10;
  52. res[i] %= 10;
  53. }
  54. }
  55.  
  56. vector<int> readNumber() {
  57. deque<int> digits;
  58. int c = getchar();
  59. while (c != '-' && !('0' <= c && c <= '9')) {
  60. c = getchar();
  61. }
  62.  
  63. if (c == '-')
  64. c = getchar();
  65.  
  66. while ('0' <= c && c <= '9')
  67. digits.push_front(c - '0'), c = getchar();
  68. return vector<int>(digits.begin(), digits.end());
  69. }
  70.  
  71. int32_t main() {
  72. ios::sync_with_stdio(false);
  73. cin.tie(nullptr);
  74. vector<int> a = readNumber();
  75. vector<int> b = readNumber();
  76. vector<int> res;
  77. multiply(a, b, res);
  78.  
  79. bool ok = false;
  80. for (int i = res.size() - 1; i >= 0; i--) {
  81. if (!ok && res[i] == 0) {
  82. continue;
  83. } else {
  84. ok = true;
  85. }
  86. cout << res[i];
  87. }
  88. if (!ok) {
  89. cout << 0;
  90. }
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment