XRay876

Untitled

Dec 1st, 2023
23
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.76 KB | None | 0 0
  1. #include <vector>
  2. #include <complex>
  3. #include <iostream>
  4. #include <math.h>
  5. #include <algorithm>
  6.  
  7. //#include <bits/stdc++.h>
  8.  
  9. #define fori(a) for(int i = 0; i < a; i++)
  10. #define forj(b) for(int j = 0; j < b; j++)
  11. #define forf(b) for(int f = 0; f < b; f++)
  12. #define forii(a, b) for(int i = a; i < b; i++)
  13. #define forjj(a, b) for(int j = a; j < b; j++)
  14. #define elif else if
  15. #define ll long long
  16.  
  17. using namespace std;
  18.  
  19.  
  20. void fast_fourier_forward(vector<complex<double>> & a) {
  21. int n = a.size();
  22. if (n == 1) {
  23. return;
  24. }
  25. vector<complex<double>> f(n/2), s(n/2);
  26. int j = 0;
  27. for (int i = 0; i < n; i += 2) {
  28. f[j] = a[i];
  29. s[j] = a[i+1];
  30. ++j;
  31. }
  32.  
  33. fast_fourier_forward(f);
  34. fast_fourier_forward(s);
  35.  
  36. double alpha = 2*M_PI/n; // бабочковый алгоритм
  37. complex<double> x(1), x_b(cos(alpha), sin(alpha));
  38. for (int i = 0; i < n/2; ++i) {
  39. a[i] = f[i] + x*s[i];
  40. a[i+n/2] = f[i] - x*s[i];
  41. x *= x_b;
  42. }
  43. }
  44.  
  45.  
  46. void fast_fourier_invert(vector<complex<double>> & a) {
  47. int n = a.size();
  48. if (n == 1) {
  49. return;
  50. }
  51. vector<complex<double>> f(n/2), s(n/2);
  52. int j = 0;
  53. for (int i = 0; i < n; i += 2) {
  54. f[j] = a[i];
  55. s[j] = a[i+1];
  56. ++j;
  57. }
  58.  
  59. fast_fourier_invert(f);
  60. fast_fourier_invert(s);
  61.  
  62. double alpha = -2*M_PI/n;
  63. complex<double> x(1), x_b(cos(alpha), sin(alpha));
  64. for (int i = 0; i < n/2; ++i) {
  65. a[i] = f[i] + x*s[i];
  66. a[i+n/2] = f[i] - x*s[i];
  67. a[i] /= 2;
  68. a[i+n/2] /= 2;
  69. x *= x_b;
  70. }
  71. }
  72.  
  73. void mult(vector<int> & a, vector<int> & b, vector<int> & res) {
  74. vector<complex<double>> a_f(a.begin(), a.end()), b_f(b.begin(), b.end());
  75. int n = 1;
  76. while (n < a.size() || n < b.size()) {
  77. n *= 2;
  78. }
  79. n *= 2;
  80. a_f.resize(n);
  81. b_f.resize(n);
  82. fast_fourier_forward(a_f);
  83. fast_fourier_forward(b_f);
  84. for (int i = 0; i < n; ++i) {
  85. a_f[i] *= b_f[i];
  86. }
  87. fast_fourier_invert(a_f);
  88. res.resize(n);
  89. for (int i = 0; i < n; ++i) {
  90. res[i] = int(a_f[i].real() + 0.5);
  91. }
  92. }
  93.  
  94.  
  95. int main() {
  96. string a, b;
  97. cin >> a >> b;
  98. if (a == "0" || b == "0") {
  99. cout <<'0';
  100. return 0;
  101. }
  102. int sign = 1;
  103. vector<int> v_a, v_b, res;
  104. if (a[0] == '-') {
  105. sign *= -1;
  106. v_a.resize(a.size()-1);
  107. for (int i = 0; i < v_a.size(); ++i) {
  108. v_a[i] = a[i+1] - '0';
  109. }
  110. } else {
  111. v_a.resize(a.size());
  112. for (int i = 0; i < v_a.size(); ++i) {
  113. v_a[i] = a[i] - '0';
  114. }
  115. }
  116.  
  117. if (b[0] == '-') {
  118. sign *= -1;
  119. v_b.resize(b.size()-1);
  120. for (int i = 0; i < v_b.size(); ++i) {
  121. v_b[i] = b[i+1] - '0';
  122. }
  123. } else {
  124. v_b.resize(b.size());
  125. for (int i = 0; i < v_b.size(); ++i) {
  126. v_b[i] = b[i] - '0';
  127. }
  128. }
  129. // cout << "Making polynom from number:";
  130. // forii(0, v_a.size()) {
  131. // cout << v_a[i] << " ";
  132. // }
  133. // cout << endl;
  134.  
  135. // double n = 5;
  136. // double alpha = 2*M_PI/n;
  137. // complex<double> x_bb(cos(alpha), sin(alpha));
  138. // cout << x_bb;
  139.  
  140. reverse(v_a.begin(), v_a.end());
  141. reverse(v_b.begin(), v_b.end());
  142. mult(v_a, v_b, res);
  143. int saved = 0, c = 0;
  144. for (int & re : res) {
  145. re += saved;
  146. saved = re / 10;
  147. re %= 10;
  148. }
  149. reverse(res.begin(), res.end());
  150. bool fl = false;
  151. if (sign == -1) {
  152. cout<<'-';
  153. }
  154. for (int & re : res) {
  155. if (!fl) {
  156. if (re != 0) {
  157. fl = true;
  158. }
  159. }
  160. if (fl) {
  161. cout << re;
  162. }
  163. }
  164. }
Add Comment
Please, Sign In to add comment