给两个n位十进制正整数x,y, 计算它们的乘积 (不含前导0). (n≤60000) 把低i位的数码看成x^i项的系数, 两个多项式相乘, 令x=10, 即得答案.
但这个 "答案" 不保证每一位是0-9, 无法输出. 所以从低到高手动进位一轮.
typedef complex<double> Complex;
const double pi = acos(-1);
const int N = (1<<17)+1;
namespace Convol {
int n, rev[N];
void init(int _n, int s)
{
n = _n;
--s;
rep (i, 1, n)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);
}
void fft(Complex a[], int d=1)
{
rep (i, 0, n)
if (rev[i] < i)
swap(a[i], a[rev[i]]);
for (int m = 1; m < n; m <<= 1) {
Complex _w(cos(pi/m), d*sin(pi/m));
for (int j = 0; j < n; j += m<<1) {
Complex w(1);
rep (k, 0, m) {
Complex t = w * a[j+m+k];
a[j+m+k] = a[j+k] - t;
a[j+k] += t;
w *= _w;
}
}
}
if (d == -1)
rep (i, 0, n) a[i] /= n;
}
void convol(Complex x[], int z[])
{
static Complex y[N];
fft(x);
rep (i, 0, n) {
int j = (n-i) & (n-1);
y[i] = Complex(0, 0.25) * (conj(x[j]*x[j]) - x[i]*x[i]);
}
fft(y, -1);
rep (i, 0, n)
z[i] = round(real(y[i]));
}
}
using Convol::convol;
Complex a[N];
int b[N];
char str[2][N];
int main()
{
int n, m = 1, s = 0;
scanf("%d ", &n);
fgets(str[0], n+2, stdin);
fgets(str[1], n+2, stdin);
while (m < 2*n-1) m <<= 1, ++s;
Convol::init(m, s);
rep (i, 0, n) a[n-1-i] = str[0][i] - '0';
rep (i, 0, n) a[n-1-i] += Complex(0, str[1][i] - '0');
convol(a, b);
rep (i, 0, 2*n-1) {
b[i+1] += b[i] / 10;
b[i] %= 10;
}
int i = 2*n;
while (i && !b[i]) --i;
while (i >= 0) putchar('0' + b[i--]);
putchar('\n');
return 0;
}