A * B Problem Plus

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 1e5+10, M = 1e3+20,inf = 2e9,mod = 1e9+7;struct Complex {    double r , i ;    Complex () {}    Complex ( double r , double i ) : r ( r ) , i ( i ) {}    Complex operator + ( const Complex& t ) const {        return Complex ( r + t.r , i + t.i ) ;    }    Complex operator - ( const Complex& t ) const {        return Complex ( r - t.r , i - t.i ) ;    }    Complex operator * ( const Complex& t ) const {        return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;    }} ;void FFT ( Complex y[] , int n , int rev ) {    for ( int i = 1 , j , t , k ; i < n ; ++ i ) {        for ( j = 0 , t = i , k = n >> 1 ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ;        if ( i < j ) swap ( y[i] , y[j] ) ;    }    for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) {        Complex wn = Complex ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , w ( 1 , 0 ) , t ;        for ( int k = 0 ; k < ds ; ++ k , w = w * wn ) {            for ( int i = k ; i < n ; i += s ) {                y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;                y[i] = y[i] + t ;            }        }    }    if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i].r /= n ;}Complex s[N*4],t[N*4];char a[N],b[N];int ans[N];int main() {    while(scanf("%s%s",a,b)!=EOF) {        int n = strlen(a);        int m = strlen(b);        int flag2 = 0, flag1 = 0;        for(int i = 0; i < n; ++i) {            if(a[i] == ‘0‘ && !flag1) {                continue;            }            else a[flag1++] = a[i];        }        for(int i = 0; i < m; ++i) {            if(b[i] == ‘0‘ && !flag2) {                continue;            }            else b[flag2++] = b[i];        }        n = flag1;        m = flag2;       // cout<<n<<" "<<m<<endl;       if(n == 0 || m == 0) {        puts("0");        continue;       }        int n1 = 1;        while(n1 <= m+n-2) n1<<=1;        for(int i = 0; i < n; ++i) {            s[i] = Complex(a[i] - ‘0‘,0);        }        for(int i = n; i < n1; ++i) {            s[i] = Complex(0,0);        }        for(int i = 0; i < m; ++i) {            t[i] = Complex(b[i] - ‘0‘,0);        }        for(int i = m; i < n1; ++i) {            t[i] = Complex(0,0);        }        FFT(s,n1,1);        FFT(t,n1,1);        for(int i = 0; i < n1; ++i) s[i] = s[i]*t[i];        FFT(s,n1,-1);        int f = 1;        int last = 0,cnt = 0;        for(int i = n+m-2; i >= 0; --i) {            int x = (int) (s[i].r+0.1) + last;           //printf("%d\n",x);            last = 0;            if(x > 9) {                last+=x/10;                ans[++cnt] = x % 10;            }            else ans[++cnt] = x;        }        if(last) {            ans[++cnt] = last;        }        for(int i = cnt; i >= 1; --i) printf("%d",ans[i]);        printf("\n");    }    return 0;}