題目內容

ZHY 有一個 \(n\) 個點的完全圖，點 \(u\) 與點 \(v\) 的距離為 \(\gcd(u,v)\)，求這個完全圖的最大生成樹的邊權之和。

思路

方法一

很明顯這道題目是在求最大生成樹，但由于數據中 $1≤n≤ 10^{7} $ ,明顯不能使用暴力枚舉每兩個點之間的 \(\gcd\)，那么我們可以從每個點 \(i\) 出發去找它的倍數 \(j\)，那 $ \gcd(i,j)=i$ ，當然由于最大生成樹要求從邊權大的邊開始加邊，所以 \(i\) 應該從 $ \frac{n}{2} $ 開始遞減尋找倍數(至于從 $ \frac{n}{2} $ 開始而不是從 \(n\) 開始是因為 $ \frac{n}{2}+1 $ 到 \(n\) 的所有數的倍數均超過了 \(n\)，無需枚舉)但這個方法的時間復雜度仍然拿不了 100pts。

方法二

在方法一的基礎上我們可以通過數論唯一分解定理，發現點 \(i\) 與點 \(j\) 之間，\(j\) 只能是 \(i\) 的質數倍，因為如果 \(j\) 是 \(i\) 的合數倍，\(j\) 就會與它的所有因數存在連邊，它的所有因數又會和 \(i\) 存在連邊，從而就形成了環，所以我們可以先進行一次歐拉篩，算出所有的質數，再從 $ \frac{n}{2} $ 開始遞減尋找質數倍數 \(j\)，跑一遍最大生成樹即可。

Code

#include <bits/stdc++.h>
using namespace std;
int n,f[10000005];
typedef long long ll; 
const int N=1e7+5;
int cnt;
int book[N],prim[N],a,b;
int getf(int x)
{
	if(f[x]==x)
		return x;
	return f[x]=getf(f[x]);
}
void ol(int x)
{
	for(ll i=2;i<=x;i++)
	{
		if(book[i]==0)
		{
			prim[++cnt]=i;
		}
		for(int j=1;1ll*i*prim[j]<=x;j++)
		{
				book[i*prim[j]]=1;
				if(i%prim[j]==0)
					break;
		}	 
	 } 
} 
int main()
{
	int sum=0;
	cin>>n;
	ol(n); 
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	long long ans=0,m=0;
	for(int i=n;i>=1;i--)
	{
		for(int j=1;prim[j]*i<=n;j++)
		{
			int fx=getf(i),fy=getf(prim[j]*i);
			if(fx!=fy)
			{
				m++;
				f[fy]=fx;
				ans+=i;
				if(m==n-1)
				{
					cout<<ans;
					return 0;
				}
			}	
		}
	}
	return 0;
}