代码

#include<cstdio>
#include<cmath>
#include<algorithm> 
#define MAXN 4000000
#define Rint register int
using namespace std;
const double PI = acos(-1);
struct complex {
    double x, y;
    complex(double _x = 0, double _y = 0): x(_x), y(_y){}
    inline complex operator = (const complex& o){
        x = o.x;y = o.y;
        return *this;
    }
    inline complex operator + (const complex& o) const {
        return complex(x + o.x, y + o.y);
    }
    inline complex operator - (const complex& o) const {
        return complex(x - o.x, y - o.y);
    }
    inline complex operator * (const complex& o) const {
        return complex(x * o.x - y * o.y, x * o.y + y * o.x);
    }
};
int limit, r[MAXN];
inline void fast_fast_tle(complex *a, int type){
    for(Rint i = 0;i < limit;i ++)
        if(i < r[i]) swap(a[i], a[r[i]]);
    for(Rint mid = 1;mid < limit;mid <<= 1){
        complex Wn(cos(PI / mid), type * sin(PI / mid));
        for(Rint j = 0;j < limit;j += mid << 1){
            complex w(1, 0);
            for(Rint k = 0;k < mid;k ++, w = w * Wn){
                complex x = a[j + k], y = w * a[j + k + mid];
                a[j + k] = x + y;
                a[j + k + mid] = x - y;
            }
        }
    }
}
int n;
char num[MAXN];
inline void init(complex *a){
    scanf("%s", num);
    for(Rint i = 0;i < n;i ++)
        a[i].x = num[n - i - 1] ^ '0';
}
int l, ans[MAXN], len;
complex a[MAXN], b[MAXN];
int main(){
    n = 1000000;
    init(a);init(b);
    for(limit = 1, l = -1;limit <= (n << 1);limit <<= 1, l ++);
    for(Rint i = 0;i < limit;i ++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << l);
    fast_fast_tle(a, 1);
    fast_fast_tle(b, 1);
    for(Rint i = 0;i <= limit;i ++)
        a[i] = a[i] * b[i];
    fast_fast_tle(a, -1);
    len = n << 1;
    for(Rint i = 0;i < len;i ++){
        ans[i] += a[i].x / limit + 0.5;
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    while(len > 1 && !ans[len - 1]) len --;
    for(Rint i = len - 1;~i;i --)
        printf("%d", ans[i]); 
}

评测结果