#include<bits/stdc++.h>
#define int long long
int p[200006],minp[200006],pcnt;
struct Prime_factor_decomposition_form{
	int size,p[18],alpha[18];
	Prime_factor_decomposition_form(){size=0;memset(p,0,sizeof(p)),memset(alpha,0,sizeof(alpha));}
};
void init()
{
	for(long long i=2;i*i<=2e9;i++)
	{
		if(!minp[i]) p[++pcnt]=i,minp[i]=i;
		for(int j=1;(long long)p[j]*p[j]*i*i<=2e9&&j<=pcnt&&p[j]<=minp[i];j++) minp[p[j]*i]=p[j];
	}
}
bool isprime(int x)
{
	if(x==2||x==3||x==5) return 1;
	if(x<6||(x%2==0||x%3==0||x%5==0)) return 0;
	for(int i=6;i*i<=x;i+=6)
		if(x%(i+1)==0||x%(i+5)==0) return 0;
	return 1;
}
Prime_factor_decomposition_form Prime_factorization(int x)
{
	Prime_factor_decomposition_form ans;
	int x1=x;
	for(int i=1;p[i]*p[i]<=x&&i<=pcnt;i++)
	{
		if(x1%p[i]==0)
		{
			ans.p[++ans.size]=p[i];
			while(x1%p[i]==0)
			{
				x1/=p[i];
				++ans.alpha[ans.size];
			}
		}
		if(x1==1) return ans;
	}
	if(isprime(x1))
	{
		ans.p[++ans.size]=x1;
		ans.alpha[ans.size]=1;
		return ans;
	}
	return ans;
}
Prime_factor_decomposition_form k[200006],sqr[200006];
int n,a[200006];
long long ans;
std::vector<long long>factor[200006];
void dfs(int num,Prime_factor_decomposition_form x,int step,long long now)
{
	if(step>x.size)
	{
		factor[num].push_back(now);
		return;
	}
	for(int j=0;j<=x.alpha[step];j++)
	{
		dfs(num,x,step+1,now);
		now*=x.p[step];
	}
	dfs(num,x,step+1,now);
}
signed main()
{
	init();
	for(int i=0;i<=2e5;i++)
	{
		k[i]=Prime_factorization(i);
		for(int j=1;j<=k[i].size;j++) sqr[i].alpha[j]=k[i].alpha[j]*2;
	}
	for(int i=0;i<=2e5;i++) dfs(i,k[i],1,1);
	for(long long i=0;i<=2e5;i++) factor[0].push_back(i);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]++;
	}
	for(long long i=0;i<=2e5;i++)
		for(long long j:factor[i])
		{
			if(i==0&&j==0)
			{
				ans+=a[0]*(a[0]-1)/2;
				continue;
			}
			if(i*i/j>2e5||j>2e5) continue;
//			if(a[(i*i/j)]&&a[j]&&i*i/j<=j) printf("%d = %d * %d,有 %d 个 %d，有 %d 个 %d\n",i*i,j,i*i/j,a[j],j,a[(i*i/j)],(i*i)/j);
			if(i!=j){if(i*i/j<j) ans+=a[(i*i/j)]*a[j];}
			else ans+=a[i]*(a[i]-1)/2;
		}
	printf("%lld",ans);
    return 0;
}

写成依托，如果这不是正解，可以说说正解是什么吗？

AC 6 WA 11