Lvat_s Blog

嗯……难度在于$O(N)-O(1)$求GCD

首先每个数都小于等于1000000

然后我们对于$1000$以内的数预处理

然后设两个数为$x$,$y$,要求的为$gcd(x,y)$

首先每个数显然最多分成3个数，每个都小于1000或者是一个质数

然后我们考虑若$d|gcd(x,y)$,那么答案可以改写成$d*gcd(x/d,y/d)$

然后对这三个数中是质数的这么复合一下，不是质数的利用$gcd(x,y)=gcd(y,x\%y)$查表即可。(因为此时拆开的$x<=1000$,所以此时$x\%y<=1000$)

最后复合其实就是乘一下……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000;

int test,n,m,gcd[N+5][N+5],a[N*2+5],b[N*2+5],pri[N*79],pcnt,f[N*N+5],vs[N*N+5][3];
unsigned int ans;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline int GCD(int x,int y){
if(!x || !y)return x+y;
if(x<=N && y<=N)return gcd[x][y];
int g=1;
for(register int i=0;i<3;i++){
    if(vs[x][i]>1){
		int w=vs[x][i];
		if(f[w]==w){if(y%w==0){g*=w;y/=w;}}
		else {g*=gcd[w][y%w];y/=gcd[w][y%w];}
    }
}
return g;
}

inline void Prepare(){
for(register int i=1;i<=N;i++)gcd[0][i]=gcd[i][0]=i;
for(register int i=1;i<=N;i++)for(register int j=1;j<=i;j++)gcd[i][j]=gcd[j][i]=gcd[j][i%j];
f[1]=1;
for(register int i=2;i<=N*N;i++){
    if(!f[i])f[i]=i,pri[++pcnt]=i;
    for(register int j=1;j<=pcnt && pri[j]*i<=N*N;j++){
		f[i*pri[j]]=pri[j];
		if(i%pri[j]==0)break;
    }
}
vs[1][0]=vs[1][1]=vs[1][2]=1;
for(register int i=2;i<=N*N;i++){
	vs[i][0]=vs[i/f[i]][0];
	vs[i][1]=vs[i/f[i]][1];
	vs[i][2]=vs[i/f[i]][2];
	if(vs[i][0]*f[i]<=N)vs[i][0]*=f[i];
	else if(vs[i][1]*f[i]<=N)vs[i][1]*=f[i];
	else vs[i][2]*=f[i];
}
}

int main(){
freopen("4454.in","r",stdin);
freopen("4454.out","w",stdout);
Read(test);
Prepare();
while(test--){
    Read(n);Read(m);ans=0;
    for(register int i=0;i<n;i++)Read(a[i]);
    for(register int i=0;i<m;i++)Read(b[i]);
    for(register int i=0;i<n;i++)for(register int j=0;j<m;j++)ans+=GCD(a[i],b[j])^i^j;
    printf("%u\n",ans);
}
return 0;
}