LOJ6487 基础FFT练习题

Link
注意到(sum a,sum ble10^6)，所以不同的(a,b)只有(10^3)级别。
因此我们预处理开根的结果，然后开桶记录有多少不同的(a,b)然后再暴力做就好了。

#include<cstdio>
#include<cctype>
using i64=long long;
const int N=1000007;
int abs(int x){return x<0? -x:x;}
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
int sqrt[N],t1[N],t2[N],a[N],b[N];
int main()
{
    for(int i=1;i<=1000;++i) sqrt[i*i]=i;
    for(int i=2;i<=1000000;++i) sqrt[i]=sqrt[i]? sqrt[i]:sqrt[i-1];
    for(int t=read();t;--t)
    {
	int n=read(),c1=0,c2=0;i64 ans=0;
	for(int i=1,k;i<=n;++i) k=read(),t1[k]++?:a[++c1]=k;
	for(int i=1,k;i<=n;++i) k=read(),t2[k]++?:b[++c2]=k;
	for(int i=1;i<=c1;t1[a[i++]]=0) for(int j=1;j<=c2;++j) ans+=1ll*t1[a[i]]*t2[b[j]]*sqrt[abs(a[i]-b[j])];
	for(int i=1;i<=c2;++i) t2[b[i]]=0;
	printf("%lld
",ans);
    }
}