define _CRT_SECURE_NO_WARNI NGS include algorithm include vector inclu

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define forn(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
//typedef complex<double> base;
struct base
{
double real;
double imag;
base() {}
base(const double real, const double imag) : real(real), imag(imag) {};
base operator + (const base & r) const {
return base(real + r.real, imag + r.imag);
}
base operator - (const base & r) const {
return base(real - r.real, imag - r.imag);
}
base operator * (const base & r) const {
return base(real * r.real - imag * r.imag,
real * r.imag + imag * r.real);
}
};
const double pi = 2 * acos(0);
const int MAXN = (int)3e6 + 10;
char a[MAXN];
char b[MAXN];
const int systpow = 5;
const int syst = pow(10, systpow) + 0.5;
base A[MAXN];
base B[MAXN];
base ww[MAXN];
int ans[MAXN * 2];
inline void fft(base* a, const int n, const bool invert)
{
for (int i = 1; i < n; ++i)
{
int j = 0;
for (int bit = 1, bitr = (n >> 1); bit < n; bit <<= 1, bitr >>= 1)
if (i & bit)
j |= bitr;
if (i < j) swap(a[i], a[j]);
}
for (int i = 0; i < n; ++i)
{
ww[i] = base(cos(i * pi * 2 / n), sin(i * pi * 2 / n));
}
for (int len = 1; len < n; len <<= 1)
{
for (int st = 0; st < n; st += 2 * len){
//base curw(1, 0);
for (int j = 0; j < len; ++j){
base curw = ww[1LL * j * n / 2 / len];
if (invert) curw = base(curw.real, -curw.imag);
base l = a[st + j];
base r = a[st + len + j] * curw;
a[st + j] = l + r;
a[st + len + j] = l - r;
}
}
}
if (invert) for (int i = 0; i < n; ++i)
{
a[i].real /= n;
a[i].imag /= n;
}
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(0);
int t;
scanf("%d\n", &t);
for (int i = 0; i < t; ++i)
{
scanf("%s %s", a, b);
//printf("%s %s\n", a, b);
int na = strlen(a);
int nb = strlen(b);
reverse(a, a + na);
reverse(b, b + nb);
int n = 1;
while (n * systpow < na || n * systpow < nb) n <<= 1;
n <<= 1;
//A.resize(n); B.resize(n);
fill(A, A + n, base(0, 0));
fill(B, B + n, base(0, 0));
for (int i = 0, pos = 0; i < na; i += systpow, ++pos)
{
int cur = 0;
for (int j = 0, p = 1; j < systpow && i + j < na; ++j, p *= 10)
cur += (a[i + j] - '0') * p;
A[pos].real = cur;
}
for (int i = 0, pos = 0; i < nb; i += systpow, ++pos)
{
int cur = 0;
for (int j = 0, p = 1; j < systpow && i + j < nb; ++j, p *= 10)
cur += (b[i + j] - '0') * p;
B[pos].real = cur;
}
fft(A, n, false);
fft(B, n, false);
for (int i = 0; i < n; ++i){
A[i] = A[i] * B[i];
}
fft(A, n, true);
ll add = 0;
int anssz = 0;
for (int i = 0; i < n; ++i){
ll cur = (ll)(A[i].real + 0.5) + add;
ans[anssz++] = cur % syst;
add = cur / syst;
}
while (anssz > 1 && ans[anssz-1] == 0)
--anssz;
reverse(ans, ans + anssz);
printf("%d", ans[0]);
for (int i = 1; i < anssz; ++i)
printf("%05d", ans[i]);
printf("\n");
}
//cout << n * 1LL * (n - 1) / 2 << endl;
//cout << stupidSolve(s) << endl;*/
return 0;
}