题解：值域分治，降低时间复杂度到 n*1000+map
代码1：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PLL;
#define IOS cin.tie(nullptr)->sync_with_stdio(false);
#define se second
#define fi first
#define mem(a,b) memset(a,b,sizeof a);
#define pri priority_queue<int,vector<int>,greater<int> >
#define low(a,b,c) lower_bound(a,a+b,c)-a;
#define upp(a,b,c) upper_bound(a,a+b,c)-a;
const int N=1e6+7;
const LL M=1e9;
vector<int > factor[N];
void init(){
for(int i = 2; i < N; i ++){
for(int j = i; j <= N; j += i){
factor[j].push_back(i);
}
}
}
LL a[N];
struct node
{
int x,y;
}e[N];
int b[N];
bool cam(node x,node y)
{
return x.y>y.y;
}
void solve()
{
int n,d;
cin>>n;
int maxx=0;
map<LL,LL> ma;
for(int i=1;i<=n;i++)
{
cin>>d;
// maxx=max(maxx,d);
ma[d]++;
}
LL ans=0;
for(auto w:ma)
{
LL j=w.fi;
LL i=w.se;
if(i>=3)
{
ans+=i*(i-1)*(i-2);
}
if(j<=1e6)
{
if(j*j<=M&&j!=1)
{
if(ma.count(j*j))
{
ans+=i*ma[j*j]*ma[1];
}
}
for(int k=2;k*k<=j;k++)
{
if(j%k!=0) continue;
LL kk=j/k;
if(ma.count(j*k)&&ma.count(j*k))
{
ans+=i*ma[j/k]*ma[j*k];
}
if(kk!=k)
{
if(ma.count(j*kk)&&ma.count(j*kk))
{
ans+=i*ma[j/kk]*ma[j*kk];
}
}
}
}
else
for(LL k=2;k*j<=M;k++)//min(j,1ll*32000)
{
if(j%k!=0) continue;
if(ma.find(j/k)==ma.end()) continue;
if(ma.find(j*k)==ma.end()) continue;
ans+=i*ma[j/k]*ma[j*k];
}
}
cout<<ans<<"\n";
}
int main()
{
// init();
IOS;
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
代码2： 没代码一快，预处理需要处理到1e6,时间更长.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PLL;
#define IOS cin.tie(nullptr)->sync_with_stdio(false);
#define se second
#define fi first
#define mem(a,b) memset(a,b,sizeof a);
#define pri priority_queue<int,vector<int>,greater<int> >
#define low(a,b,c) lower_bound(a,a+b,c)-a;
#define upp(a,b,c) upper_bound(a,a+b,c)-a;
const int N=1e6+7;
const LL M=1e9;
vector<int > factor[N];
void init(){
for(int i = 2; i < N; i ++){
for(int j = i; j <= N; j += i){
factor[j].push_back(i);
}
}
}
LL a[N];
struct node
{
int x,y;
}e[N];
int b[N];
bool cam(node x,node y)
{
return x.y>y.y;
}
void solve()
{
int n,d;
cin>>n;
int maxx=0;
map<LL,LL> ma;
for(int i=1;i<=n;i++)
{
cin>>d;
// maxx=max(maxx,d);
ma[d]++;
}
LL ans=0;
for(auto w:ma)
{
LL j=w.fi;
LL i=w.se;
if(i>=3)
{
ans+=i*(i-1)*(i-2);
}
if(j<=1e6)
{
// for(auto w:factor[j]);
if(j==1) continue;
for(auto v:factor[j])
{
if(v*j<=M&&ma.count(j/v)&&ma.count(j*v)) ans+=i*ma[j/v]*ma[j*v];
}
// if(j*j<=M&&j!=1)
// {
// if(ma.count(j*j))
// {
// ans+=i*ma[j*j]*ma[1];
// }
// }
// for(int k=2;k*k<=j;k++)
// {
// if(j%k!=0) continue;
// LL kk=j/k;
// if(ma.count(j*k)&&ma.count(j*k))
// {
// ans+=i*ma[j/k]*ma[j*k];
// }
// if(kk!=k)
// {
// if(ma.count(j*kk)&&ma.count(j*kk))
// {
// ans+=i*ma[j/kk]*ma[j*kk];
// }
// }
// }
}
else
for(LL k=2;k*j<=M;k++)//min(j,1ll*32000)
{
if(j%k!=0) continue;
if(ma.find(j/k)==ma.end()) continue;
if(ma.find(j*k)==ma.end()) continue;
ans+=i*ma[j/k]*ma[j*k];
}
}
cout<<ans<<"\n";
}
int main()
{
init();
// for(auto v:factor[8]) cout<<v<<endl;
IOS;
int t=0;
cin>>t;
while(t--)
{
solve();
}
return 0;
}