D. MST in Modulo Graph 详细题解

这是一道数论 + 最小生成树（Kruskal）+ 贪心 + 优化建图的经典难题。

---

一、题目回顾

给定 $n$ 个点，点权 $p_i$。 任意两点 $x,y$ 之间的边权为：

$$w(x,y) = \max(p_x,p_y) \bmod \min(p_x,p_y)$$

求这张完全图的最小生成树（MST）权值和。

---

二、核心数学公式

对两个正整数 $a>b$：

$$a \bmod b = a - k \cdot b$$

其中 $k = \lfloor \frac{a}{b} \rfloor$。

最重要结论：

1. 如果 $b \mid a$（$a$ 是 $b$ 的倍数）$$a \bmod b = 0$$ ✅ 这是权值最小的边（0）！
2. 否则$$a \bmod b = a - kb > 0$$

👉 贪心策略：MST 优先选权值为 0 的边！

---

三、标程整体算法框架

1. 去重 + 排序点权
2. 预处理：每个数 x 的倍数附近最小存在的数
3. 建边：
   - 相同数：边权 0
   - 倍数关系：边权 0
   - 接近倍数：边权 a mod b
4. Kruskal 算法求 MST（并查集 DSU）

---

四、标程逐段详细解析

1. 变量与结构体

const int N=5e5+55;
int MAXN=0;
int n,tot,ans,maxx,f[N],siz[N],p[N],bj[N],pre[N],suf[N],pos[N];
struct node{ int from,to,dis; } a[N*20];

• p[]：点权
• bj[x]：标记 $x$ 是否在数组中出现
• pre[], suf[]：数论优化，找最近存在数
• pos[x]：数值 $x$ 对应的点编号
• a[]：存储所有边
• f[], siz[]：并查集

2. 并查集（DSU）模板

int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(siz[x]<siz[y])swap(x,y);
    siz[x]+=siz[y],f[y]=x;
}

标准路径压缩 + 按秩合并，保证复杂度。

---

3. 每组测试用例初始化

tot=ans=maxx=0;
memset 清空所有数组
n=read();
for(int i=1;i<=n;i++){
    p[i]=read();
    bj[p[i]]=1;         // 标记存在
    maxx=max(maxx,p[i]);// 最大权值
}
sort(p+1,p+n+1);        // 排序！关键优化

---

4. 数论预处理：pre / suf（核心优化）

// pre[i] = ≤i 的最大存在数
for(int i=1;i<=maxx;i++){
    if(bj[i])pre[i]=i;
    else pre[i]=pre[i-1];
}
// suf[i] = ≥i 的最小存在数
for(int i=maxx;i>=1;i--){
    if(bj[i])suf[i]=i;
    else suf[i]=suf[i+1];
}

作用：快速找到某个数附近最小存在的数 用于构造权值尽可能小的边。

---

5. 建边（最核心！）

for(int i=1;i<=n;i++) pos[p[i]]=i; // 数值→点编号

for(int i=1;i<=n;i++){
    // 情况1：和前一个数相同 → 边权 0
    if(p[i]==p[i-1]){
        a[++tot]={i,i-1,0};
        continue;
    }
    // 情况2：枚举倍数 k*p[i]，找最优边
    for(int k=1;k*p[i]<=maxx;k++){
        // 如果 k*p[i] 存在 → 边权 0
        if(bj[k*p[i]] && k!=1){
            a[++tot]={pos[k*p[i]],i,0};
            continue;
        }
        // 否则找倍数区间内最近的数
        int L = k*p[i]+1;
        int R = (k+1)*p[i];
        int tmy = suf[L];
        if(tmy > R) continue;
        // 边权 = tmy mod p[i]
        int cost = tmy - k*p[i];
        a[++tot]={pos[tmy],i,cost};
    }
}

建边规则（标程核心思想）

对每个数 $x = p[i]$：

1. 相同数字：连边权 $0$
2. $x$ 的倍数：连边权 $0$
3. 接近 $x$ 倍数的数：连边权 $a \bmod x$（最小可能正权）

👉 这样建边不会丢失最优边！ 👉 边数从 $O(n^2)$ 压到 $O(n\log M)$

---

6. Kruskal 求 MST

sort(a+1,a+tot+1,cmp); // 按边权从小到大
for(int i=1;i<=n;i++) f[i]=i,siz[i]=1;

for(int i=1;i<=tot;i++){
    int u = a[i].from;
    int v = a[i].to;
    int w = a[i].dis;
    if(find(u) != find(v)){
        merge(u,v);
        ans += w;
    }
}
cout<<ans<<endl;

贪心选最小边，用并查集判连通，累加权值。

---

五、算法复杂度

• 建边：$O(n \log M)$
• Kruskal：$O(n \log n)$
• 总复杂度：$O(\sum n \log M)$

满足：

• $n \le 5 \times 10^5$
• $\sum n \le 5 \times 10^5$
• $\sum \max(p_i) \le 5 \times 10^5$

---

六、样例解释（对照标程）

输入：

5
4 3 3 4 4

排序后：3,3,4,4,4

建边：

• 3 ↔ 3：权 0
• 4 ↔ 4：权 0
• 3 与 4 接近倍数关系：权 1

MST 仅需一条权 1 边，其余都是 0，答案 = 1 ✔

---

七、完整标程

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<ctime>
#include<bitset>
#include<set>
#include<math.h>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define vi vector<int>
#define vl vector<long long>
#define ci ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
int read(){
	char c=getchar();
	ll x=1,s=0;
	while(c<'0'||c>'9'){
	   if(c=='-')x=-1;c=getchar();
	}
	while(c>='0'&&c<='9'){
	   s=s*10+c-'0';c=getchar();
	}
	return s*x;
}
const int N=5e5+55;
int MAXN=0;
int n,tot,ans,maxx,f[N],siz[N],p[N],bj[N],pre[N],suf[N],pos[N];
struct node{
	int from,to,dis;
}a[N*20];
int cmp(node x,node y){
	return x.dis<y.dis;
}
int find(int x){
	if(f[x]!=x)return f[x]=find(f[x]);
	else return x;
}
void merge(int x,int y){
	x=find(x);y=find(y);
	if(siz[x]<siz[y])swap(x,y);
	siz[x]+=siz[y];
	f[y]=x;
}
int T;
int main(){
	T=read();
	while(T--)
	{
		tot=ans=maxx=0;
		for(int i=1;i<=MAXN;++i)
		{
			f[i]=siz[i]=p[i]=bj[i]=pre[i]=suf[i]=pos[i]=0;
		}
		for(int i=0;i<=MAXN*19;++i)
		a[i].from=a[i].to=a[i].dis=0;
		
		n=read();
		MAXN=n;
		for(int i=1;i<=n;i++)p[i]=read(),bj[p[i]]=1,maxx=max(maxx,p[i]),MAXN=max(MAXN,p[i]);
		sort(p+1,p+n+1);
		for(int i=1;i<=maxx;i++){
			if(bj[i])pre[i]=i;
			else pre[i]=pre[i-1];
		}
		for(int i=maxx;i>=1;i--){
			if(bj[i])suf[i]=i;
			else suf[i]=suf[i+1];
		}
		for(int i=1;i<=n;i++)pos[p[i]]=i;
		for(int i=1;i<=n;i++){
			if(p[i]==p[i-1]){
				a[++tot]={i,i-1,0};
				continue;
			}
			for(int k=1;k*p[i]<=maxx;k++){
				int tmy=0;
				if(bj[k*p[i]] and k!=1){
					a[++tot]={pos[k*p[i]],i,0};
					continue;
				}
				if(suf[k*p[i]+1]<=(k+1)*p[i])tmy=suf[k*p[i]+1];
				if(!tmy)continue;
				int cost=abs(k*p[i]-tmy);
				a[++tot]={pos[tmy],i,cost};
			}
		}
		sort(a+1,a+tot+1,cmp);
		for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;
		for(int i=1;i<=tot;i++){
			if(find(a[i].from)!=find(a[i].to)){
				merge(a[i].from,a[i].to);
				ans+=a[i].dis;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

---

八、总结（最关键的 3 句话）

1. 边权 $\max(a,b) \bmod \min(a,b)$ 最小值是 $0$（倍数/相同数）
2. 标程只建权值 0 和接近 0 的边，不建完全图
3. Kruskal + 并查集 得到 MST，就是答案