abc230g

rt，求大佬证明下面的做法的正确性或错误性。

先筛出质数和所有数的质因数、因数。

然后从小到大遍历所有质数倍数位置，并记录位置上的数的因数。

然后遍历所有出现过的因数 $fac_i$，如果是质数则说明有以它为公因数的数对存在，则答案加上 $fac_i$ 出现过的次数 $\frac{cnt_i \times (cnt_i-1)}{2}$。

如果因数不是质数且只有次数为 $1$ 的质因子，说明它已经被算过了，答案减去上面的式子。

如果因数不是质数且有次数大于 $1$ 的质因子，说明它已经在“只有次数为 $1$ 的质因子的部分被减过了，不管。

最后答案还要加上 $(i,i)$ 数对的数量。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,a[200010],fac[200010],p[2000010],pcnt;
long long ans,t[200010];
vector<int>v[200010];
int id[200010],cnt,pf[200010];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=2;i<=n;i++)
	{
		if(!fac[i])p[++pcnt]=i;
		for(int j=1;i*j<=n;j++)
		{
			if(!fac[i*j])fac[i*j]=i;
			v[i*j].push_back(i);
		}
	}
	for(int i=1;i<=pcnt;i++)
		for(int j=2;j*p[i]<=n;j++)
			pf[j*p[i]]++;
	for(int i=1;i<=pcnt;i++)
	{
		if(p[i]>n)break;
		cnt=0;
		for(int j=p[i];j<=n;j+=p[i])
		{
			for(int k:v[a[j]])
			{
				if(!t[k])id[++cnt]=k;
				t[k]++;
			}
		}
		for(int j=1;j<=cnt;j++)
		{
			if(pf[id[j]]==0)ans+=(t[id[j]]*(t[id[j]]-1)/2);
			else if(pf[id[j]]==v[id[j]].size()-1)
				ans-=(pf[id[j]]-1)*(t[id[j]]*(t[id[j]]-1)/2);
			t[id[j]]=0;
		}
	}
	printf("%lld",ans+n-2);
	return 0;
}