#P1919. 【模板】A*B Problem 升级版(FFT 快速傅里叶变换)

【模板】A*B Problem 升级版(FFT 快速傅里叶变换)

题目背景

本题数据已加强,请使用 FFT/NTT,不要再交 Python 代码浪费评测资源。

题目描述

给你两个正整数 a,ba,b,求 a×ba \times b

输入格式

第一行一个正整数,表示 aa
第二行一个正整数,表示 bb

输出格式

输出一行一个整数表示答案。

114514 
1919810
219845122340

提示

【数据范围】
1a,b1010000001\le a,b \le 10^{1000000}

可能需要一定程度的常数优化。
数据由 NaCly_Fish 重造