Codeforces Round 867 (Div. 3) - G2. Magic Triples (Hard Version)

思路：与G1唯一不同的是值域上界ulim变成了1e9，若我们还是按照原先做法 O ( n ∗ u l i m ) O(n*\sqrt{ulim}) O(n∗ulim ​),TLE，向大佬学习了一下，学到了值域分治！！！ orz %%%

令mxm = 1e6，

对于$x<mxm$的数，我们考虑直接暴力分解，复杂度是 O ( x ) O(\sqrt{x}) O(x ​)，最大有1e3，接下来枚举x的因子，即按照G1思路

对于$x>=mxm$的数，我们考虑到上界是1e9，可以直接去顺序枚举因子i，由于 $i\ast x<=ulim$，所以时间复杂度为$O(ulim/x)$，至多1e3

当时$x=mxm$时，2项都是1e3左右，不足以被卡

ps：对于$x>=mxm$统计答案时要先判断 i 是否 x 的因子,不然会TLE， 个人理解是 x mod i 为0先保证了i是x的因子，可以先把不是因子的舍去，但是如果在后面写x%i==0由于map好像本身查找也有一点时间复杂度，然后就会爆

Code：

#include 
//#define int long long
#define rep(i,a,n) for(int i=a; i<=n; i++)
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
using namespace std;const int mxn=2e5+10, mxm=1e6, ulim=1e9;
int a[mxn];
vector<int> rs(int x){vector<int> v;for(int i=1; i*i<=x; i++){if(x%i==0){v.pb(i);if(i!=x/i) v.pb(x/i);}}sort(v.begin(),v.end());return v;
}
void solve(){auto get_same=[&](int x)-> long long{return 1ll*x*(x-1)*(x-2);};int n;cin>>n;map<int,int> Mp;rep(i,1,n) cin>>a[i], Mp[a[i]]++;long long ans=0;for(auto &[x,y]:Mp){ans+=get_same(y);if(x<=mxm){auto v=rs(x);for(auto it:v){if(it==1) continue;//因子为1已经统计过if(1ll*it*x>ulim) break;if(Mp.count(x/it)&&Mp.count(x*it)){ans+=1ll*y*Mp[x/it]*Mp[x*it];}}}else{for(int i=2; 1ll*i*x<=ulim; i++){if(x%i==0){if(Mp.count(x/i)&&Mp.count(x*i)){ans+=1ll*y*Mp[x/i]*Mp[x*i];}}}}}cout<<ans<<'\n';
}
signed main(){ios;int t=1;cin>>t;while(t--){solve();}return 0;		
}