wmq的A×B Problem
题目链接：http://oj.xjtuacm.com/problem/13/
题目大意：$T$组数据，每组给出$n$个数$a_i$及一个素数$m$，求这$n$个数两两相乘模$m$余$k$有多少个（$0\leqslant k < m$）.
数论+FFT
原根的概念
设$n \geqslant 1$，$(a,n)=1$，使得$a^d \equiv 1(mod n)$成立的最小的正整数$d$，被称为$a$对模$n$的阶，记做$\delta_n(a)$.
当$\delta_n(a)=\varphi(n)$时，称$a$为模$n$的一个原根.
一些性质
1.质数必存在原根（有缘再证）；
2.若$(a,n)=1$，$a^d \equiv 1 (mod n)$，则$\delta_n(a)|d$.
证明：设$d=k\delta_n(a)+r$，其中$0 \leqslant r < \delta_n(a)$，则有
$a^d \equiv a^{k\delta_n(a)+r} \equiv a^r \equiv 1(mod n)$.
由$\delta_n(a)$的最小性得，$r=0$.
$\therefore \delta_n(a)|d$.
2.若$(a,n)=1$，$a^k \equiv a^l (mod n)$，则$k \equiv l(mod \delta_n(a))$.
证明：不妨设$k \geqslant l$，则有$a^{k-l} \equiv 1 (mod n)$.
$\because \delta_n(a)|k-l$.
$\therefore k \equiv l(mod \delta_n(a))$.
3.若$(a,n)=1$，则$a^0,a^1,...,a^{\delta_n(a)-1}$模$n$两两不同余。特别地，当$a$为$n$的原根时，这$\varphi(n)$个数是模$n$的一个缩系.
证明：假设存在$0 \leqslant k,l < \delta_n(a)$，使得$a^k \equiv a^l (mod n)$.
由2.知，$k \equiv l (mod \delta_n(a))$.
$\therefore a^0,a^1,...a^{\delta_n(a)-1}$两两不同余。
当$a$是模$n$的原根时，$\delta_n(a) = \varphi(n)$，故这$\varphi(n)$个数是模$n$的一个缩系.
因为题目中$m$为质数，故必存在原根，设其中一个原根为$r$。
将模$m$为零的数单独处理：$ans[0]=mod[0] \times (n-mod[0])+mod[0] \times (mod[0]-1)/2$;
将所有的模m不为零的数$a_i$写成$r^x$的形式，从而构造出一个关于$r$的多项式：$S=\sum_{i=0}^{\varphi(m)-1}A_ir^i$.
考虑任意两个数的乘积$r^i \times r^j = r^{i+j}$，将多项式$S$作平方，删去多余项（直接相乘包含了$a_i \times a_i$的结果），即为答案.
复杂度为$O(\varphi(m) \times lg(\varphi(m)) )$.
代码如下：
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 #include <cstring>
5 #define N 60010
6 using namespace std;
7 typedef long long ll;
8 ll T,n,m,t,r,len,phi;
9 ll ans[N],mod[N],rt[N],temp[4*N];
10 const double pi=acos(-1.0);
11 struct Complex{
12 double r,i;
13 Complex(double r=0,double i=0):r(r),i(i){};
14 Complex operator+(const Complex &rhs){return Complex(r+rhs.r,i+rhs.i);}
15 Complex operator-(const Complex &rhs){return Complex(r-rhs.r,i-rhs.i);}
16 Complex operator*(const Complex &rhs){return Complex(r*rhs.r-i*rhs.i,i*rhs.r+r*rhs.i);}
17 }a[4*N],b[4*N],c[4*N];
18 void sincos(double theta,double &p0,double &p1){
19 p0=sin(theta);p1=cos(theta);
20 }
21 void fft_main(Complex P[], ll n, ll oper){
22 for(ll i=1,j=0;i<n-1;i++){
23 for(ll s=n;j^=s>>=1,~j&s;);
24 if(i<j)swap(P[i],P[j]);
25 }
26 Complex unit_p0;
27 for(ll d=0;(1<<d)<n;d++){
28 ll m=1<<d,m2=m*2;
29 double p0=pi/m*oper;
30 sincos(p0,unit_p0.i,unit_p0.r);
31 for(ll i=0;i<n;i+=m2){
32 Complex unit=1;
33 for(ll j=0;j<m;j++){
34 Complex &P1=P[i+j+m],&P2=P[i+j];
35 Complex t=unit*P1;
36 P1=P2-t; P2=P2+t;
37 unit=unit*unit_p0;
38 }
39 }
40 }if(oper==-1)for(ll i=0;i<len;i++)P[i].r/=len;
41 }
42 void fft(Complex a[],Complex b[],ll len){
43 fft_main(a,len,1);fft_main(b,len,1);
44 for(ll i=0;i<len;++i)c[i]=a[i]*b[i];
45 fft_main(c,len,-1);
46 }
47 void fft_init(){
48 len=1;
49 while(len<2*phi)len<<=1;
50 ll i=0;
51 for(ll x=1;i<phi;++i){
52 rt[i]=mod[x];
53 a[i].r=b[i].r=rt[i];
54 a[i].i=b[i].i=0;
55 x=(x*r)%m;
56 }
57 for(;i<len;++i){
58 a[i].r=b[i].r=0;
59 a[i].i=b[i].i=0;
60 }
61 }
62 ll powmod(ll a,ll n,ll m){
63 ll r=1,t=a;
64 while(n){
65 if(n&1)r=(r*t)%m;
66 t=(t*t)%m;
67 n>>=1;
68 }
69 return r;
70 }
71 ll Root(ll m){
72 for(ll i=2,j;i<m;++i){
73 for(j=2;j<phi;++j)
74 if(powmod(i,j,m)==1)
75 break;
76 if(j==phi)return i;
77 }
78 return 0;
79 }
80 ll in(){
81 ll res=0,flag=0,ch;
82 if((ch=getchar())=='-')flag=1;
83 else if('0'<=ch&&ch<='9')res=ch-'0';
84 while('0'<=(ch=getchar())&&ch<='9')res=res*10+ch-'0';
85 return flag?-res:res;
86 }
87 void out(ll x){
88 if(x>9)out(x/10);
89 putchar(x%10+'0');
90 }
91 void solve(){
92 for(ll i=0;i<len;++i){
93 temp[i]=c[i].r+0.5;
94 temp[i]/=2;
95 }
96 for(ll i=0;i<phi;++i){
97 temp[2*i]-=rt[i]*rt[i]/2;
98 temp[2*i]+=rt[i]*(rt[i]-1)/2;
99 }
100 for(ll i=0,x=1;i<len;++i){
101 ans[x]+=temp[i];
102 x=(x*r)%m;
103 }
104 ans[0]=mod[0]*(n-mod[0])+mod[0]*(mod[0]-1)/2;
105 }
106 void init(){
107 memset(temp,0,sizeof(temp));
108 n=in();m=in();
109 for(ll i=0;i<m;++i)mod[i]=0;
110 for(ll i=0;i<m;++i)ans[i]=0;
111 for(ll i=0;i<n;++i){
112 t=in();
113 mod[t%m]++;
114 }
115 }
116 int main(void){
117 T=in();
118 while(T--){
119 init();
120 phi=m-1;
121 r=Root(m);
122 fft_init();
123 fft(a,b,len);
124 solve();
125 for(ll i=0;i<m;++i){
126 out(ans[i]);
127 puts("");
128 }
129 }
130 }