CF1822G2 - Magic Triples

比较好的题目，别的不说，G1 对 G2 有着不错的启发性。

首先，因为 \(b>0,a_k\le 10^9\)，所以 \(b\) 不可能超过 \(\sqrt{a}\)

考虑对 \(b\) 分类讨论，设置一个阈值 \(B\)，先处理 \(b=1\) 的情况，其实就是取三个相同的数然后排列，可以比较简单的排序之后做到 \(O(n)\)。

接着手写一个哈希表用来存所有 \(a_i\) 出现次数。

然后考虑 \(1\lt b\le B\)，这种情况下我们可以遍历枚举 \(i\)，然后在哈希表中查询 \(ba_i\) 和 \(b^2a_i\) 出现的次数乘起来，注意不要乘上 \(a_i\) 出现的次数，因为每个 \(a_i\) 都会贡献一次。

然后分析 \(b\gt B\) 的情况，我们发现这时候因为 \(a_k\le 10^9\)，所以 \(a_j\le 10^9/B\)，那么我们就先枚举 \(a_j\)，然后对于满足条件的 \(a_j\) 枚举因子作为 \(b\)，一共有大约 \(\sqrt{10^9/B}\) 个。对于其所有大于 \(b\) 的因子，都尝试将其作为 \(b\)，找到 \(a_i/b\) 和 \(ba_i\) 的出现次数乘起来即可。

记 \(B\) 为对 \(b\) 分治的长度，复杂度为 \(O(nB+n\sqrt{\dfrac{a_{max}}{B}})\)

此时取 \(B=a_{max}^{1/3}=1000\) 最优，足以通过此题。

const int N=200005,A=1000000000,B=1000;
ll n,a[200005];
struct hash_table{
	#define S 19198100
	vector<int>used;
	int sz=0,hd[S+5],id[N],nxt[N],w[N];
	inline void ins(int k){
		int u=k%S;
		for(int i=hd[u];i;i=nxt[i])if(id[i]==k)return (void)(w[i]++);
		++sz,nxt[sz]=hd[u],w[sz]=1,id[sz]=k,hd[u]=sz;
		used.push_back(u);
	}
	inline int qry(int k){
		for (int i=hd[k%S];i;i=nxt[i])if(id[i]==k)return w[i];
		return 0;
	}
	inline void flush(){
		sz=0;
		for(int i:used)hd[i]=0;
		used.clear();
	}
}h;
inline void solve(){
	cin>>n;
	rp(i,n)cin>>a[i];
	h.flush();
	rp(i,n)h.ins(a[i]);
	ll ans=0;
	map<ll,ll>mp;
	rp(i,n)mp[a[i]]++;
	for(auto i:mp)ans+=i.second*(i.second-1)*(i.second-2);
	rep(i,2,B){
		rp(j,n)if(a[j]*i*i<=A){
			ans+=h.qry(a[j]*i)*h.qry(a[j]*i*i);
		} 
	}
	rep(i,1,n)if(a[i]<=A/B){
		for(ll j=1;j*j<=a[i];j++)if(a[i]%j==0){
			if(a[i]*j<=A&&j>B)ans+=h.qry(a[i]/j)*h.qry(a[i]*j);
			if(a[i]*(a[i]/j)<=A&&a[i]/j>B)ans+=h.qry(j)*h.qry(a[i]*(a[i]/j));
		}
	}cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	rd(_,t)solve();
	return 0;
}
//Crayan_r