XJTUOJ13 （数论+FFT）

http://oj.xjtuacm.com/problem/13/

题意：wmq如今开始学习乘法了！他为了训练自己的乘法计算能力，写出了n个整数，

　　　并且对每两个数a,b都求出了它们的乘积a×b。现在他想知道，在求出的n(n-1)/2个乘积中，

　　　除以给定的质数m余数为k(0≤k<m)的有多少个。

　　　对每组数据输出m行，其中第i行为除以m余数为(i-1)的有多少个。

　　　第一行为测试数据的组数。

　　　对于每组测试数据，第一行为2个正整数n,m,2≤n,m≤60000，分别表示整数的个数以及除数。

　　　接下来一行有n个整数，满足0≤ai≤1e9。

　　　保证总输出行数∑m≤3e5。

分析：首先对于输入的a[i]，我们肯定先模m一下

　　　然后我们关心的就变成了0~m-1中的数各自有多少个

　　　然后就是处理两个这样的数组“相乘”

　　　和FFT十分类似，但是这里并不是i+j=k，而是i*j=k，那么怎么办呢？

　　　注意到模数是个素数，所以一定有原根x

　　　那么就说明x^1,x^2,...,x^i,...,x^m-1和1,2,3,4,...m-1肯定一一对应

　　　那么我们可以把数字映射成x^i，那么相乘问题就变成了指数的相加

　　　就可以用FFT做了

　　　至于0的情况，特判就ok了

巴特西