JZOJ5888. 【NOIP2018模拟9.29】GCD生成樹

題解

考慮最暴力的一種做法，直接将邊全部建出來，這顯然是不行的。

考慮克魯斯卡爾的做法，

将邊權從小到大加入，

而且這裡的最大邊權并不大，就可以直接枚舉。

假設現在枚舉了邊權v，

那麼， a i a_i ai​為v，2v，3v，…兩兩之間連邊的邊權就可以為v。

其實不用擔心2v與4v的邊權不是為v的這個問題，

因為在枚舉邊權為2v的時候就已經将他們連起來了。

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#define ll long long
#define N 100003
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
	n=0;
	ch=G();
	while((ch<'0' || ch>'9') && ch!='-')ch=G();
	ll w=1;
	if(ch=='-')w=-1,ch=G();
	while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
	n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int n,a[N],mx,m,f[N],s,x,y,id[N];
ll ans;

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

int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	
	read(n);ans=m=s=0;
	for(int i=1;i<=n;i++)
	{
		read(a[i]),mx=max(mx,a[i]);
		if(id[a[i]])f[i]=id[a[i]],ans=ans+a[i],m++;
			else f[i]=id[a[i]]=i;
	}
		
	for(int i=mx;i && m<n-1;i--)
	{
		s=x=0;
		for(int j=1;j*i<=mx;j++)
		{
			if(!id[j*i])continue;
			y=get(id[j*i]);
			if(x==0)x=y;else if(x!=y)s++,f[y]=x;
		}
		ans=ans+(ll)i*s;
		m=m+s;
	}
	
	printf("%lld",ans);
	return 0;
}