wmq的A×B Problem

发布时间: 2017年4月9日 17:06   最后更新: 2017年4月9日 17:07   时间限制: 3000ms   内存限制: 512M

描述

这是一个非常简单的问题。

wmq如今开始学习乘法了！他为了训练自己的乘法计算能力，写出了n个整数，并且对每两个数a,b都求出了它们的乘积a×b。现在他想知道，在求出的n(n−1)2个乘积中，除以给定的质数m余数为k(0≤k<m)的有多少个。

输入

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

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

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

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

输出

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

样例输入1

24 52 0 1 74 22 0 1 6

样例输出1

3020160

 

题解：

　　m是素数，显然，利用原根性质

　　i -> g^i

　　此时g为m的原根

　　首先 模剩余系 为0~m-1，那么模为 i * j 转化为 g^(i+j)

　　即FFT求解，NTT也可过

　　最后转化回来即可

#include
       
        using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair
        
         #define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 333333+10, M = 1e3+20,inf = 2e9,mod = 469762049;int MOD;inline int mul(int a, int b){    return (long long)a * b % MOD;}int power(int a, int b){    int ret = 1;    for (int t = a; b; b >>= 1){        if (b & 1)ret = mul(ret, t);        t = mul(t, t);    }    return ret;}int cal_root(int mod){    int factor[20], num = 0, s = mod - 1;    MOD = mod--;    for (int i = 2; i * i <= s; i++){        if (s % i == 0){            factor[num++] = i;            while (s % i == 0)s /= i;        }    }    if (s != 1)factor[num++] = s;    for (int i = 2;; i++){        int j = 0;        for (; j < num && power(i, mod / factor[j]) != 1; j++);        if (j == num)return i;    }}struct Complex {    long double r , i ;    Complex () {}    Complex ( double r , double i ) : r ( r ) , i ( i ) {}    Complex operator + ( const Complex& t ) const {        return Complex ( r + t.r , i + t.i ) ;    }    Complex operator - ( const Complex& t ) const {        return Complex ( r - t.r , i - t.i ) ;    }    Complex operator * ( const Complex& t ) const {        return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;    }} ;void FFT ( Complex y[] , int n , int rev ) {    for ( int i = 1 , j , t , k ; i < n ; ++ i ) {        for ( j = 0 , t = i , k = n >> 1 ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ;        if ( i < j ) swap ( y[i] , y[j] ) ;    }    for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) {        Complex wn = Complex ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , w ( 1 , 0 ) , t ;        for ( int k = 0 ; k < ds ; ++ k , w = w * wn ) {            for ( int i = k ; i < n ; i += s ) {                y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;                y[i] = y[i] + t ;            }        }    }    if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i].r /= n ;}Complex s[N];int T,n,m,x,num[N];LL ans[N],mo[N],fmo[N];int main() {    scanf("%d",&T);    while(T--) {        scanf("%d%d",&n,&m);        int G = cal_root(m);        for(LL i = 0, t = 1; i < m-1; ++i,t = t*G%m)            mo[i] = t,fmo[t] = i;        memset(num,0,sizeof(num));        LL cnt0 = 0;        for(int i = 0; i <= m; ++i) ans[i] = 0;        for(int i = 1; i <= n; ++i) {            scanf("%d",&x);            x%=m;            if(x == 0) cnt0++;            else {                num[fmo[x]]++;            }        }        int n1 = 1;        for(n1=1;n1<=(2*m-2);n1<<=1);        for(int i = 0; i < m; ++i) s[i] = Complex(num[i],0);        for(int i = m; i < n1; ++i) s[i] = Complex(0,0);        FFT(s,n1,1);        for(int i = 0; i < n1; ++i) s[i] = s[i]*s[i];        FFT(s,n1,-1);        printf("%lld\n",(LL)cnt0*(n-cnt0)+(LL)cnt0*(cnt0-1)/2);        for(int i = 0; i <= 2*m-2; ++i) {            LL now = (LL)(s[i].r+0.5);            if(i%2==0) now -= num[i/2];            now/=2;            ans[mo[i%(m-1)]] += now;        }        for(int i = 1; i < m; ++i) printf("%lld\n",ans[i]);    }    return 0;}
        
       

 

　　

 

#include
       
        using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair
        
         #define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 533333+10, M = 1e3+20,inf = 2e9;int MOD;inline int mul2(int a, int b){    return (long long)a * b % MOD;}int power(int a, int b){    int ret = 1;    for (int t = a; b; b >>= 1){        if (b & 1)ret = mul2(ret, t);        t = mul2(t, t);    }    return ret;}int cal_root(int mod){    int factor[26], num = 0, s = mod - 1;    MOD = mod--;    for (int i = 2; i * i <= s; i++){        if (s % i == 0){            factor[num++] = i;            while (s % i == 0)s /= i;        }    }    if (s != 1)factor[num++] = s;    for (int i = 2;; i++){        int j = 0;        for (; j < num && power(i, mod / factor[j]) != 1; j++);        if (j == num)return i;    }}LL P,G;LL mul(LL x,LL y){    return (x*y-(LL)(x/(long double)P*y+1e-3)*P+P)%P;}LL qpow(LL x,LL k,LL p){    LL ret=1;    while(k){        if(k&1) ret=mul(ret,x);        k>>=1;        x=mul(x,x);    }    return ret;}LL wn[50];void getwn(){    for(int i=1; i<=25; ++i){        int t=1<
         
          >1,k; i
          
           >1;        while(j>=k){            j-=k;            k>>=1;        }        if(j
           
            >1); ++j){                LL u=y[j],t=mul(y[j+h/2],w);                y[j]=u+t;                if(y[j]>=P) y[j]-=P;                y[j+h/2]=u-t+P;                if(y[j+h/2]>=P) y[j+h/2]-=P;                w=mul(w,wn[id]);            }        }    }    if(op==-1){        for(int i=1; i
            
             < m; ++i) s[i] = num[i]; for(int i = m; i < len; ++i) s[i] = 0; NTT_init(); NTT(s,1); for(int i = 0; i < len; ++i) s[i] = mul(s[i],s[i]); NTT(s,-1); for(int i = 0; i <= 2*m-2; ++i) { LL now = s[i]; if(i%2==0) now -= num[i/2]; now /= 2; ans[mo[i%(m-1)]] += now; } printf("%lld\n",(LL)cnt0*(n-cnt0)+(LL)cnt0*(cnt0-1)/2); for(int i = 1; i < m; ++i) printf("%lld\n",ans[i]); } return 0;}