526互联

G2 - Magic Triples (Hard Version)

发布时间 2023-04-28 20:46:08作者: xxj112

题解：值域分治，降低时间复杂度到 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;
}