代码

#pragma GCC optimize("O3,unroll-loops,omit-frame-pointer")
#pragma GCC target("arch=skylake")

#include <math.h>
#include <stdio.h>

struct C { double r, i; };

enum { N = 1 << 19, DIGITS = 1000000, GROUP = 4, BASE = 10000 };

static C a[N];
static unsigned long long c[N];
static char input[2000016];
static char output[2000016];

static inline C mul(C x, C y) {
    return {x.r * y.r - x.i * y.i, x.r * y.i + x.i * y.r};
}

static void fft(C *x, int inverse) {
    for (unsigned i = 1, j = 0; i < N; ++i) {
        unsigned bit = N >> 1;
        while (j & bit) { j ^= bit; bit >>= 1; }
        j ^= bit;
        if (i < j) { C t=x[i]; x[i]=x[j]; x[j]=t; }
    }
    const double pi = 3.141592653589793238462643383279502884;
    for (unsigned len = 2; len <= N; len <<= 1) {
        double ang = (inverse ? 2.0 : -2.0) * pi / len;
        C step = {cos(ang), sin(ang)};
        unsigned h = len >> 1;
        for (unsigned p = 0; p < N; p += len) {
            C w = {1.0, 0.0};
            for (unsigned j = 0; j < h; ++j) {
                if ((j & 63u) == 0) {
                    double x = ang * j;
                    w = {cos(x), sin(x)};
                }
                C u=x[p+j], v=mul(x[p+j+h],w);
                x[p+j]={u.r+v.r,u.i+v.i};
                x[p+j+h]={u.r-v.r,u.i-v.i};
                w=mul(w,step);
            }
        }
    }
    if (inverse) {
        const double q=1.0/N;
        for (unsigned i=0;i<N;++i) { x[i].r*=q; x[i].i*=q; }
    }
}

static void read_number(const char *s, int imaginary) {
    unsigned limb=0;
    for (int end=DIGITS; end>0; end-=GROUP,++limb) {
        int begin=end>=GROUP?end-GROUP:0;
        unsigned v=0;
        for(int i=begin;i<end;++i)v=v*10+(unsigned)(s[i]-'0');
        if(imaginary)a[limb].i=v;else a[limb].r=v;
    }
}

int main() {
    size_t got=fread(input,1,sizeof(input),stdin);
    if(got<2000001)return 1;
    read_number(input,0);
    read_number(input+DIGITS+1,1);
    fft(a,0);
    a[0]={a[0].r*a[0].i,0};
    a[N/2]={a[N/2].r*a[N/2].i,0};
    for(unsigned k=1;k<N/2;++k){
        C x=a[k], y={a[N-k].r,-a[N-k].i};
        C av={(x.r+y.r)*.5,(x.i+y.i)*.5};
        C bv={(x.i-y.i)*.5,(y.r-x.r)*.5};
        C z=mul(av,bv);
        a[k]=z;a[N-k]={z.r,-z.i};
    }
    fft(a,1);
#ifdef LOCAL_DEBUG
    for (unsigned i=0;i<20;++i) fprintf(stderr,"%u %.9f\n",i,a[i].r);
#endif
    unsigned nc=2*((DIGITS+GROUP-1)/GROUP);
    unsigned long long carry=0;
    for(unsigned i=0;i<nc;++i){
        unsigned long long v=(unsigned long long)(a[i].r+.5)+carry;
        c[i]=v%BASE;carry=v/BASE;
    }
    while(carry){c[nc++]=carry%BASE;carry/=BASE;}
    while(nc>1&&!c[nc-1])--nc;
    char *p=output;
    p += sprintf(p,"%llu",c[--nc]);
    while(nc){unsigned v=(unsigned)c[--nc];*p++=(char)('0'+v/1000);*p++=(char)('0'+v/100%10);*p++=(char)('0'+v/10%10);*p++=(char)('0'+v%10);}
    *p++='\n';
    fwrite(output,1,(size_t)(p-output),stdout);
    return 0;
}

评测结果