首页 > 代码库 > wmq的A×B Problem

wmq的A×B Problem

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 #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 }

 

wmq的A×B Problem