1 /**************************************************************  2     Problem: 2179  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:616 ms  7     Memory:24248 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 #define complex P 15 using namespace std; 16 typedef double lf; 17 typedef long long ll; 18 const int N = 300005; 19 const lf pi = acos(-1); 20   21 struct complex { 22     lf x, y; 23     P() {} 24     P(lf _x, lf _y) : x(_x), y(_y) {} 25       26     P operator + (const P &b) { 27         return P(x + b.x, y + b.y); 28     } 29     P operator - (const P &b) { 30         return P(x - b.x, y - b.y); 31     } 32     P operator * (const P &b) { 33         return P(x * b.x - y * b.y, x * b.y + y * b.x); 34     } 35 } x[N], y[N], w[2][N]; 36   37 int n, k; 38 ll a[N], b[N]; 39   40 void read(ll *a) { 41     int i, now = ceil((lf) n / 2) - 1; 42     char ch = getchar(); 43     while (ch < ‘0‘ || ‘9‘ < ch) ch = getchar(); 44     for (i = n; i; --i) { 45         (a[now] *= 10) += ch - ‘0‘; 46         ch = getchar(); 47         if (i & 1) --now; 48     } 49 } 50   51 void print(ll *a, int n) { 52     printf("%lld", a[n--]); 53     for (; ~n; --n) 54         printf("%02lld", a[n]); 55 } 56   57   58 void FFT(P *x, int k, int v) { 59     int i, j, l; 60     P tmp; 61     for (i = j = 0; i < k; ++i) { 62         if (i > j) swap(x[i], x[j]); 63         for (l = k >> 1; (j ^= l) < l; l >>= 1); 64     } 65     for (i = 2; i <= k; i <<= 1) 66         for (j = 0; j < k; j += i) 67             for (l = 0; l < i >> 1; ++l) { 68                 tmp = x[j + l + (i >> 1)] * w[v][k / i * l]; 69                 x[j + l + (i >> 1)] = x[j + l] - tmp; 70                 x[j + l] = x[j + l] + tmp; 71             } 72 } 73   74 void work() { 75     int i; 76     for (k = 1; k < n << 1; k <<= 1); 77     for (i = 0; i <= k; ++i) 78         w[1][k - i] = w[0][i] = P(cos(pi * 2 * i / k), sin(pi * 2 * i / k)); 79     for (i = 0; i < k; ++i) 80         x[i] = P(a[i], 0); 81     FFT(x, k, 0); 82     for (i = 0; i < k; ++i) 83         y[i] = P(b[i], 0); 84     FFT(y, k, 0); 85     for (i = 0; i < k; ++i) 86         x[i] = x[i] * y[i]; 87     FFT(x, k, 1); 88     for (i = 0; i < 2 * k; ++i) 89         a[i] = (int) (x[i].x / k + 0.5); 90     for (i = 0; i < 2 * k - 1; ++i) 91         a[i + 1] += a[i] / 100, a[i] %= 100; 92     for (k = 2 * k - 1; !a[k]; --k); 93     print(a, k); 94 } 95   96 int main() { 97     int i; 98     scanf("%d", &n); 99     read(a), read(b);100     n = ceil((lf) n / 2);101     work();102     return 0;   103 }