主题

主题

 
   

2179: FFT快速傅立叶

Description

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

Input

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

Output

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

Sample Input

1

3

4

Sample Output

12

数据范围:

n<=60000


个人解法:

第一次拿FFT做题(模板题不算),甚是兴奋。蒟蒻纪念一下。

关于此题,我们只需要视多项式的x为10,那么就是这个高精度数字了。

于是可以在O(nlogn)实现。


代码如下:

https://code.csdn.net/snippets/2249932

 
 
评论