wmq的A×B Problem

题目链接：

题目大意：$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 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           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
         
          >=1,~j&s;); 24         if(i
          
           >=1; 68 } 69 return r; 70 } 71 ll Root(ll m){ 72 for(ll i=2,j;i
           
            9)out(x/10); 89 putchar(x%10+'0'); 90 } 91 void solve(){ 92 for(ll i=0;i