Eva

Description

给出两个n位10进制整数x和y，你需要计算x*y。

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

输出一行，即x*y的结果。

1
3
4

12
数据范围：
n<=60000

/**************************************************************

    Problem: 2179

    User: mywaythere

    Language: C++

    Result: Accepted

    Time:956 ms

    Memory:11352 kb

****************************************************************/

 

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

 

using namespace std;

 

struct cplx {

    double r, i;

    inline cplx(double r0 = 0, double i0 = 0) {

        r = r0, i = i0;

    }

    inline cplx operator +(const cplx& a) {

        return cplx(r + a. r, i + a. i);

    }

    inline cplx operator -(const cplx& a) {

        return cplx(r - a. r, i - a. i);

    }

    inline cplx operator *(const cplx& a) {

        return cplx(r * a. r - i * a. i, r * a. i + i * a. r);

    }

};

 

const int maxn = 200009;

const double pi = asin(1) * 2;

 

char a[maxn], b[maxn];

int l, n, s[maxn];

cplx x[maxn], y[maxn], z[maxn];

 

void rader(cplx* a, int n) {

    for (int i = 1,  j = n >> 1, k; i < n - 1; ++ i) {

        if (i < j)

            swap(a[i], a[j]);

        k = n >> 1;

        while (j >= k) {

            j -= k;

            k >>= 1;

        }

        if (j < k)

            j += k;

    }

}

 

void fft(cplx* a, int n, bool d) {

    rader(a, n);

    for (int h = 2; h <= n; h <<= 1) {

        cplx w0(cos(pi * 2 / (double)h), sin(pi * 2 / (double)h));

        if (d)

            w0. i = -w0. i;

        for (int i = 0; i < n; i += h) {

            cplx w(1, 0);

            for (int j = i; j < i + (h >> 1); ++ j) {

                cplx x = a[j], y = a[j + (h >> 1)] * w;

                a[j] = x + y;

                a[j + (h >> 1)] = x - y;

                w = w * w0;

            }

        }

    }

}

 

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

 

    scanf("%d%s%s", &l, a, b);

    for (n = 1; n <= l * 2; n <<= 1);

    for (int i = 0; i < l; ++ i) {

        x[i] = cplx(a[l - i - 1] - 48, 0);

        y[i] = cplx(b[l - i - 1] - 48, 0);

    }

    fft(x, n, 0);

    fft(y, n, 0);

    for (int i = 0; i < n; ++ i)

        z[i] = x[i] * y[i];

    fft(z, n, 1);

    for (int i = 0; i < n; ++ i)

        s[i] = (int)(z[i]. r / n + 0.499);

    for (int i = 0; i < n; ++ i) {

        s[i + 1] += s[i] / 10;

        s[i] %= 10;

    }

    int t = n - 1;

    while (!s[t] && t)

        -- t;

    for (int i = t; i >= 0; -- i)

        putchar(s[i] + 48);

    putchar(10);

}