day2-命运石之门（卷积）

出题人题解：
对质数P，计算其原根为g。这样可以将ai写成g^bi的形式。于是乘法就变成了质数的加法，直接利 用FFT进行计算即可。需要注意的是要对ai = 0的情况特殊处理。

my answer：

原根的性质忘了，先跳过（qaq），总之可以[1,p-1]的ai全映射成了[1,p-1]的bi。

令f（x）为对于b_x的答案，g（i）为数字i的个数，

可得卷积：f（x）=sum{ g(i)*g(x-i)，i=0,1,2...x }

由卷积定理可得：f（x）=IDFT[  DFT（g(x)）*DFT（g(x)） ]

p<=2e5，那么先用哈希表求出g（x），再对2e5个数做DFT，O(N)相乘后，再IDFT，得到f（x），在f（x）中寻找对应的答案即可，总复杂度就是DFT和IDFT的复杂度O(nlogn)

代码待补