出题人题解 | #简单数学题#

原题解链接：https://ac.nowcoder.com/discuss/157310

由题面可知$t=f(x)\backslash \; t=f(x)$没有平方根，加上$xx$的最大质因子为$7171$，说明它的质因子种数只有$2020$种。 那么$t=f(x)\backslash \; t=f(x)$可映射成一个$2020$位的二进制数。 即 $t=p_0\ast b_0+p_1\ast b_1+\mathrm{.}\mathrm{.}\mathrm{.}+p_k\ast b_{k}t=p\_\{0\}*b\_\{0\}+p\_\{1\}*b\_\{1\}+...+p\_\{k\}*b\_\{k\}$

其中 $p_i\backslash \; p\_\{i\}$ 为第$i\backslash \; i$大的素数，$b_i\backslash \; b\_\{i\}$ 为第$i\backslash \; i$位二进制位， 我们不妨设$bin(t)=p_k\mathrm{.}\mathrm{.}\mathrm{.}{p}_1{p}_{0}bin(t)\; =\; p\_\{k\}...p\_\{1\}p\_\{0\}$

则$bin(g(f(x_1),f(x_2),f(x_3)))=bin(f(x_1))\oplus bin(f(x_2))\oplus bin(f(x_3))bin(g(f(x\_\{1\}),f(x\_\{2\}),f(x\_\{3\})))\; =\; bin(f(x\_\{1\}))\backslash oplus\; bin(f(x\_\{2\}))\; \backslash oplus\; bin(f(x\_\{3\}))$

那么对于$z\backslash \; z$来说，它的表示方法的种数有 $num(z)={\sum }_{i\oplus j\oplus k=bin(z)}An[i]\ast Bn[j]\ast Cn[k]num(z)\; =\; \backslash sum\_\{i\; \backslash oplus\; j\; \backslash oplus\; k=bin(z)\}\{An[i]*Bn[j]*Cn[k]\}$ 其中 $An[i]\backslash \; An[i]$为$AA$数组中经过$binbin$映射后等于i的个数， $Bn[j]\backslash \; Bn[j]$为$BB$数组中经过$binbin$映射后等于$jj$的个数，$Cn[k]\backslash \; Cn[k]$为$CC$数组中经过$binbin$映射后等于$kk$的个数。

这里再用卷积加速即可。

#include <stdio.h>
#define rep(i, j, k) for(int i = (j); i <= (k); ++i)
typedef long long ll;
const int MOD = 1e9 + 7;
const int rev = (MOD + 1) / 2;
int p[105], a[3][(1 << 22)];
void FWT(int a[],int n){
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++){
                int x=a[i+j],y=a[i+j+d];
				a[i+j]=(x+y)%MOD,a[i+j+d]=(x-y+MOD)%MOD;
            }
}
void UFWT(int a[], int n) {
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++){
                int x=a[i+j],y=a[i+j+d];
				a[i+j]=1ll*(x+y)*rev%MOD,a[i+j+d]=(1ll*(x-y+MOD)%MOD*rev%MOD)%MOD;
            }
}
void solve(int a[],int b[],int n){
    FWT(a,n);
    FWT(b,n);
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%MOD;
    UFWT(a,n);
}
int main(){
	int c = 0;
	rep(i, 2, 71){
		bool flag = true;
		rep(j, 2, i - 1) if(i % j == 0) flag = false;
		if(flag) p[c++] = i;
	}
	int n; scanf("%d", &n);
	rep(k, 0, 2) rep(i, 1, n){
		ll t; scanf("%lld", &t);
		int x = 0; rep(j, 0, c-1) if(t % p[j] == 0) x |= (1 << j);
		a[k][x]++;
//		printf("t:%lld x:%d\n", t, x);
	}
//	rep(k, 0, 2) rep(j, 0, 1<<c) printf("%d%c", a[k][j], " \n"[j==(1<<c)]);
	solve(a[0], a[1], (1 << c));
//	rep(k, 0, 2) rep(j, 0, 1<<c) printf("%d%c", a[k][j], " \n"[j==(1<<c)]);
	solve(a[0], a[2], (1 << c));
//	rep(k, 0, 2) rep(j, 0, 1<<c) printf("%d%c", a[k][j], " \n"[j==(1<<c)]);
	int ans = 0;
	rep(i, 0, (1 << c) - 1){
		int x = 1;
		rep(j, 0, c - 1) if(i >> j & 1) x = (ll)x * p[j] % MOD;
//		if(a[0][i]) printf("x:%d c:%d\n", x, a[0][i]);
		ans = (ans + (ll)x * a[0][i] % MOD) % MOD;
	}
	printf("%d\n", ans);
	return 0;

}