A * B Problem Plus

  1 #include <string>  2 #include <vector>  3 #include <algorithm>  4 #include <numeric>  5 #include <set>  6 #include <map>  7 #include <queue>  8 #include <iostream>  9 #include <sstream> 10 #include <cstdio> 11 #include <cmath> 12 #include <ctime> 13 #include <cstring> 14 #include <cctype> 15 #include <cassert> 16 #include <limits> 17 #include <bitset> 18 #include <complex> 19 #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) 20 #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) 21 #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) 22 #define all(o) (o).begin(), (o).end() 23 #define rall(o) (o).rbegin(), ((o).rend()) 24 #define pb(x) push_back(x) 25 #define mp(x,y) make_pair((x),(y)) 26 #define mset(m,v) memset(m,v,sizeof(m)) 27 #define INF 0x3f3f3f3f 28 #define INFL 0x3f3f3f3f3f3f3f3fLL 29 using namespace std; 30 typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; 31 typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll; 32 typedef vector<string> vs; typedef long double ld; 33 template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; } 34 template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; } 35  36 typedef long double Num;    //??????long double????? 37 const Num PI = 3.141592653589793238462643383279L; 38 typedef complex<Num> Complex; 39 //n????? 40 //a????? 41 void fft_main(int n, Num theta, Complex a[]) { 42     for(int m = n; m >= 2; m >>= 1) { 43         int mh = m >> 1; 44         Complex thetaI = Complex(0, theta); 45         rep(i, mh) { 46             Complex w = exp((Num)i*thetaI); 47             for(int j = i; j < n; j += m) { 48                 int k = j + mh; 49                 Complex x = a[j] - a[k]; 50                 a[j] += a[k]; 51                 a[k] = w * x; 52             } 53         } 54         theta *= 2; 55     } 56     int i = 0; 57     reu(j, 1, n-1) { 58     for(int k = n >> 1; k > (i ^= k); k >>= 1) ; 59         if(j < i) swap(a[i], a[j]); 60     } 61 } 62  63 void fft(int n, Complex a[]) { fft_main(n, 2 * PI / n, a); } 64 void inverse_fft(int n, Complex a[]) { fft_main(n, -2 * PI / n, a); } 65  66 void convolution(vector<Complex> &v, vector<Complex> &w) { 67     int n = 1, vwn = v.size() + w.size() - 1; 68     while(n < vwn) n <<= 1; 69     v.resize(n), w.resize(n); 70     fft(n, &v[0]); 71     fft(n, &w[0]); 72     rep(i, n) v[i] *= w[i]; 73     inverse_fft(n, &v[0]); 74     rep(i, n) v[i] /= n; 75 } 76  77 const int maxn = 50005; 78 vector<int> ans; 79 char s1[maxn], s2[maxn]; 80  81 void solve(vector<int> &res) {     82     //cerr << s1 << s2; 83     int len1 = strlen(s1), len2 = strlen(s2); 84     for (int i = 0; i < len1; i++) s1[i] -= ‘0‘; 85     for (int i = 0; i < len2; i++) s2[i] -= ‘0‘; 86     vector<Complex> Lc(len1), Rc(len2); 87     for (int i = 0; i < len1; i++) Lc[i] = Complex(s1[len1-i-1], 0); 88     for (int i = 0; i < len2; i++) Rc[i] = Complex(s2[len2-i-1], 0); 89     convolution(Lc, Rc); 90     int n = len1 + len2 - 1; 91     res.resize(n); 92     rep(i, n) res[i] = Lc[i].real() + .5; 93 } 94  95 int main(void) { 96     while (~scanf("%s %s", s1, s2)) { 97         solve(ans); 98         ans.resize(ans.size() << 1); 99         for (int i = 0; i < ans.size(); i++) {100             ans[i+1] += ans[i] / 10;101             ans[i] %= 10;102         }103         int high = ans.size() - 1;104         while (high > 0 && !ans[high]) high--;105         for (int i = high; i >= 0; i--) putchar(ans[i] + ‘0‘);106         putchar(‘\n‘);107     }108     return 0;109 }