G2
考虑按值域分治
将 \(x\) 当作中间的数
如果 \(x \leq 10^6\) , 直接根号复杂度枚举其因子即可
如果 \(x > 10^6\) , 注意到一个数的上限是 \(10^9\) , 直接从 \([1,1000]\) 枚举 \(b\) 即可
#include <bits/stdc++.h>
using ll = long long;
void solve()
{
int n;
std::cin >> n;
std::set<int> p;
std::map<int,int> mp;
for(int i = 0 ; i < n ; ++i) {
int x ; std::cin >> x ;
p.insert(x); mp[x] ++;
}
ll ans = 0;
int lim = 1E6 , INF = 1E9;
for(auto x : p) {
if (x <= lim) {
for(int b = 1 ; b * b <= x ; ++b) {
if(x % b == 0) {
if(mp.count(x / b) && mp.count(x * b) ) {
if(b != 1) ans += 1ll * mp[x / b] * mp[x] * mp[x * b];
else {
if(mp[x] >= 3) ans += 1ll * mp[x] * ( mp[x] - 1 ) * (mp[x] - 2);
}
}
int _b = x / b;
if(_b != b && x <= INF / _b && mp.count(x / _b) && mp.count(x * _b))
ans += 1ll * mp[x / _b] * mp[x] * mp[x * _b];
}
}
}
else {
for(int b = 1 ; b <= 1000 ; ++b) {
if(x % b == 0 ) {
if(x <= INF / b && mp.count(x / b) && mp.count(x * b)) {
if(b != 1 ) ans += 1ll * mp[x / b] * mp[x] * mp[x * b];
else {
if(mp[x] >= 3) {
ans += 1ll * mp[x] * (mp[x] - 1) * (mp[x] - 2);
}
}
}
}
}
}
}
std::cout << ans << '\n';
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}