题解：CF1822G2 Magic Triples (Hard Version)

tkdqmx · 2026-01-27 11:08:44 · 题解

Easy Version 时可以枚举中间数并 O(\sqrt{V}) 枚举因数 b 计算答案。

Hard Version 中直接枚举中间数的做法当 a_i>10^6 时会 TLE，考虑基于此优化。

发现 \frac{10^9}{10^6}=10^3=\sqrt{10^6}，所以 a_i>10^6 时将枚举因数改为枚举倍数即可。

由于值域过大，使用 map 存储信息，注意这题使用 unordered_map 会神秘 TLE。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
int t,n,ans,a[N];map<int,int> mp;
int count(int x){return mp.count(x)?mp[x]:0;}
void solve(){
    cin>>n,ans=0,mp.clear();
    for(int i=1;i<=n;i++)  cin>>a[i],mp[a[i]]++;
    for(auto [x,y]:mp){
        ans+=y*(y-1)*(y-2);
        if(x!=1)  ans+=count(1)*count(x*x)*y;
        if(x<=1000000)  for(int i=2;i*i<=x;i++){
            if(x%i!=0)  continue;
            ans+=count(x/i)*count(x*i)*y;
            if(i*i==x)  continue;
            ans+=count(i)*count(x*x/i)*y;
        }
        else  for(int i=2;i*x<=1000000000;i++){
            if(x%i!=0)  continue;
            ans+=count(x/i)*count(x*i)*y;
        }
    }
    return cout<<ans<<"\n",void();
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>t;while(t--)  solve();
}