Description：

给定一个 $n$ 个点的完全无向图，每条边的边权是两端点点权的 $\gcd$ ，求这个图的最大生成树。

$1\leqslant n\leqslant 10^5,1\leqslant a[i]\leqslant 10^5$

Solution：

首先直接求出所有边做生成树复杂度不会小于 $O(n^2)$ ，考虑更玄学的做法，先把所有相等的点合到一起，因为在这两个点和别的点合并的时候边权一定 $\leqslant $ 这两个点的值，枚举每个数作为 $\gcd$ ，然后把所有他的倍数还没有连起来的连起来，这样连起来的一定是 $\gcd$ ，因为 $\gcd$ 的倍数早就在之前被连起来了，顺便统计一下边权即可。时间复杂度调和级数 $O(n\ln n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

typedef long long ll;

ll ans = 0;

int tot = 0;

int v[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int main()

{

	freopen("gcd.in","r",stdin);

	freopen("gcd.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)

	{

		if(v[a[i]] == 0)v[a[i]] = ++tot;

		else ans += a[i];

	}

	for(int i = 1;i <= tot;++i)f[i] = i;

	for(int i = 50000;i >= 1;--i)

	{

		int cur = 0;

		for(int j = i;j <= 100000;j += i)

		{

			if(v[j] == 0)continue;

			if(cur == 0)cur = v[j];

			else

			{

				int p = find(cur),q = find(v[j]);

				if(p != q)

				{

					ans += i;

					f[p] = q;

				}

			}

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}