Steins；Gate(NEUQ OJ)

Gate(NEUQ OJ)"/>

Steins；Gate(NEUQ OJ)

链接：NEUQ OJ

题意：给定一个数组 a , 对于每个 ak 求有多少对（ i , j ）满足 a[i] * a[j]%P = a[k] ; ( i , j , k 可以相同)

分析：对于P，求出它的原根 ( 不知道的话可以去搜一下，不难理解 )，这样 a[i] 就可以表示成 g^b[i];

则  a[i] * a[j]%P = a[k] 

  g^(b[i]+b[j]) % P = g^b[k] 

  b[i] + b[j] = b[k] ；

这样就转变成了 加法问题，就可以用 FFT 加速求解了。

注意对 a[i]=0 的情况要特殊处理。

代码：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const double PI=acos(-1.0);struct Complex
{double r,i;Complex(double _r=0,double _i=0){r=_r,i=_i;}Complex operator + (const Complex &b){return Complex(r+b.r,i+b.i);}Complex operator - (const Complex &b){return Complex(r-b.r,i-b.i);}Complex operator * (const Complex &b){return Complex(r*b.r-i*b.i,r*b.i+i*b.r);}
}; void change(Complex y[],int len)
{int i,j,k;for(i=1,j=len/2;i<len-1;i++){if(i<j) swap(y[i],y[j]);k=len/2;while(j>=k){j-=k;k/=2;}if(j<k) j+=k;}
}void fft(Complex y[],int len,int on)
{change(y,len);for(int h=2;h<=len;h<<=1){Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j=0;j<len;j+=h){Complex w(1,0);for(int k=j;k< j+h/2;k++){Complex u=y[k];Complex t=w*y[k+h/2];y[k]=u+t;y[k+h/2]=u-t;w=w*wn;}}}if(on==-1)for(int i=0;i<len;i++)y[i].r/=len;
}ll qpow(ll n,ll m,ll p)
{ll ans=1;n%=p;for(;m;m>>=1,n=n*n%p)if(m&1)ans=ans*n%p;return ans;
}const int N = 2*1e5+10;ll pri[2*N]; int tot=0;ll getRoot(ll p) //求质数p的最小原根
{tot=0;ll n=p-1,sq=sqrt(p+0.5);for(int i=2;i<=sq;i++)if(n%i==0){pri[tot++]=i;while(n%i==0)n/=i;}if(n>1)pri[tot++]=n;for(int g=2;g<=p-1;g++) //试探每一个g是否原根{int flag=1;for(int i=0;i<tot;i++)if(qpow(g,(p-1)/pri[i],p)==1){flag=0; break;}if(flag)return g;}return -1; //没有原根
}Complex x[N*4];
ll a[N],b[N];
ll num[N*4];
int I[N];int main()
{int n,P;ll zero;while(~scanf("%d%d",&n,&P)){zero=0;int g = getRoot(P);int tmp=1; for(int i=1;i<P;i++){tmp=tmp*g%P;I[tmp]=i;}I[1]=0;// I[g^i] = i memset(num,0,sizeof(num));for(int i=0;i<n;i++){scanf("%lld",&a[i]);b[i]=a[i]%P;if(b[i]) num[I[b[i]]]++;else  zero++;}int len=1,len1=P-1;while(len<2*len1) len<<=1;for(int i=0;i<len1;i++) x[i]=Complex(num[i],0);for(int i=len1;i<len;i++) x[i]=Complex(0,0);fft(x,len,1);for(int i=0;i<len;i++) x[i]=x[i]*x[i];fft(x,len,-1);for(int i=0;i<len;i++) num[i]=(ll)(x[i].r+0.5);// FFT 常规操作 for(int i=P-1;i<len;i++) num[i%(P-1)]+=num[i];  for(int i=0;i<n;i++){if(a[i]>=P) putchar('0');   // a[i]>=P 的话取模没有意义，故为0  else if(b[i]) printf("%lld",num[I[b[i]]]); else printf("%lld",2*zero*(n-zero)+zero*zero);// b[i]为0 则（i，j）的取法有两类，i,j其中一个为0，或者两个都为0  puts("");}}return 0;
}