题解

题目描述

给定一个长度为 $n$ 的整数数组 $\{a_1,a_2,\ldots,a_n\}$ 以及一个整数 $k$。对数组中的任意两个不同数字 $a_i$ 与 $a_j$，如果方程

存在至少一组正整数解（即 $x>0,y>0$），则在图中将对应的两个点连接一条边，且边的权值为该方程正整数解的组数。构造的图可能由多个连通块组成，小美只关注点数最多的连通块。在这个连通块上，从所有可能的生成树中选出总权值最小的那棵，并输出该最小权值。

思路

1. 判断正整数解存在性与计算解的个数
   对于任意两个不同的数 $a_i$ 与 $a_j$，令 $d=\gcd(a_i,a_j)$。

   • 如果 $d$ 不能整除 $k$，则方程无整数解。

   • 若 $d$ 整除 $k$，令
     $a'$=$\frac{a_i}{d}$,$b'=\frac{a_j}{d}$,$k'=\frac{k}{d}$
     则原方程可化为
     $a' \times x$ + $b' \times y$ = $k'$
     且 $\gcd(a',b')=1$。

     利用扩展欧几里得算法求得一组特解 $(x_0,y_0)$，使得

     $$a' \times x_0 + b' \times y_0 = 1.$$

     乘以 $k'$ 后得到

     $$x = x_0 k',\quad y = y_0 k',$$

     为一组特解。

     该方程的通解为
     $x = x_0 k' + b' \times t$,$\quad y = y_0 k' - a' \times t$,$\quad t \in \mathbb{Z}.$

     要求 $x>0$ 与 $y>0$，必须满足
     $x_0 k'$ + $b' \times t$ > 0,$\quad y_0 k'$ - $a' \times t$ > $0.$

     从而可以求出 $t$ 的最小取值 $t_{min}$ 与最大取值 $t_{max}$。注意由于 $a'$ 与 $b'$ 均为正整数，为了避免整数除法对负数向零截断的问题，我们采用浮点数计算后取整：
     $t_{min}$ = $\lfloor -\frac{x_0 k'}{b'}$$\rfloor + 1$,$\quad t_{max}$ = $\lceil \frac{y_0 k'}{a'} \rceil - 1.$

     如果 $t_{min} \le t_{max}$，则正整数解的个数为

     $$cnt = t_{max} - t_{min} + 1.$$

2. 图的构造与求解最小生成树

   • 枚举所有 $\binom{n}{2}$ 对 $(a_i,a_j)$，对于满足条件的对，建立一条边，其边权即为上述计算得到的 $cnt$。
   • 利用并查集对所有节点进行分块，然后找出节点数最多的连通块。
   • 对于该连通块（如果有多个点数最多的连通块，任选其一），使用 Kruskal 算法求出该连通块上生成树的最小权值。若连通块只有一个节点，则输出 $0$。

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath> // 包含 floor 与 ceil
using namespace std;
typedef long long ll;

// 扩展欧几里得算法，求 a*x + b*y = gcd(a, b) 的一组解
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = ext_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

// 并查集结构
struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void merge(int x, int y) {
        x = find(x); y = find(y);
        if(x != y) parent[y] = x;
    }
};

// 边结构体
struct Edge {
    int u, v;
    ll w;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; ll k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<Edge> edges;
    // 枚举所有点对
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            ll ai = a[i], aj = a[j];
            ll d = std::gcd(ai, aj);
            // 若 k 不能被 d 整除，则无解
            if(k % d != 0) continue;
            ll a1 = ai / d, b1 = aj / d, k1 = k / d;
            // 扩展欧几里得算法求特解：a1 * x0 + b1 * y0 = 1
            ll x0, y0;
            ext_gcd(a1, b1, x0, y0);
            // 得到特解: x0 * k1, y0 * k1
            x0 *= k1; y0 *= k1;
            // 通解： x = x0 + b1 * t,  y = y0 - a1 * t, t ∈ ℤ
            // 要求 x > 0 与 y > 0，即：
            // x0 + b1 * t > 0   -->  t > -x0 / b1
            // y0 - a1 * t > 0   -->  t < y0 / a1
            // 利用浮点数计算避免整数除法的截断问题：
            ll t_min = (ll)floor(- (double)x0 / b1) + 1;
            ll t_max = (ll)ceil((double)y0 / a1) - 1;
            if(t_min > t_max) continue;
            ll cnt = t_max - t_min + 1;
            edges.push_back({i, j, cnt});
        }
    }
    
    // 用并查集求所有点的连通分量
    DSU dsu(n);
    for(auto &e: edges){
        dsu.merge(e.u, e.v);
    }
    // 统计每个连通分量的大小
    vector<int> compSize(n, 0);
    for(int i = 0; i < n; i++){
        compSize[dsu.find(i)]++;
    }
    int maxSize = 0;
    for(int i = 0; i < n; i++){
        maxSize = max(maxSize, compSize[i]);
    }
    // 找出所有点数最多的连通块
    vector<int> maxComponents;
    for(int i = 0; i < n; i++){
        if(dsu.find(i) == i && compSize[i] == maxSize){
            maxComponents.push_back(i);
        }
    }
    
    ll ans = -1;
    // 对每个最大连通块，使用 Kruskal 算法求最小生成树
    for(auto comp: maxComponents){
        // 收集该连通块的所有节点
        vector<int> nodes;
        for(int i = 0; i < n; i++){
            if(dsu.find(i) == comp) nodes.push_back(i);
        }
        // 标记哪些节点在该连通块内
        vector<bool> inComp(n, false);
        for(auto u: nodes) inComp[u] = true;
        // 构造该连通块内的边
        vector<Edge> compEdges;
        for(auto &e: edges){
            if(inComp[e.u] && inComp[e.v]) {
                compEdges.push_back(e);
            }
        }
        // 若连通块只有一个点，则生成树权值为 0
        if(nodes.size() == 1){
            ans = (ans == -1 ? 0 : min(ans, (ll)0));
            continue;
        }
        // Kruskal 算法求 MST
        sort(compEdges.begin(), compEdges.end(), [](const Edge &a, const Edge &b){
            return a.w < b.w;
        });
        DSU dsu2(n);
        ll sum = 0;
        int cnt = 0;
        for(auto &e: compEdges){
            int ru = dsu2.find(e.u), rv = dsu2.find(e.v);
            if(ru != rv) {
                dsu2.merge(ru, rv);
                sum += e.w;
                cnt++;
                if(cnt == (int)nodes.size() - 1) break;
            }
        }
        if(cnt == (int)nodes.size() - 1){
            if(ans == -1) ans = sum;
            else ans = min(ans, sum);
        }
    }
    cout << ans << "\n";
    return 0;
}

Python

import sys
import math
from math import gcd
sys.setrecursionlimit(1000000)

# 扩展欧几里得算法，求 a*x + b*y = gcd(a, b) 的一组解
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return d, x, y

# 并查集实现
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def merge(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.parent[ry] = rx

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:2+n]))
    
    edges = []
    # 枚举所有点对
    for i in range(n):
        for j in range(i+1, n):
            ai = a[i]
            aj = a[j]
            d = math.gcd(ai, aj)
            if k % d != 0:
                continue
            a1 = ai // d
            b1 = aj // d
            k1 = k // d
            # 扩展欧几里得算法求特解：a1 * x0 + b1 * y0 = 1
            d_val, x0, y0 = ext_gcd(a1, b1)
            # 特解乘以 k1 得到 a1 * (x0*k1) + b1 * (y0*k1) = k1
            x0 *= k1
            y0 *= k1
            # 通解: x = x0 + b1 * t, y = y0 - a1 * t, t ∈ ℤ
            # 要求 x > 0 与 y > 0，即:
            # x0 + b1 * t > 0  -->  t > -x0 / b1
            # y0 - a1 * t > 0  -->  t < y0 / a1
            # 利用浮点数计算避免截断问题
            t_min = math.floor(-x0 / b1) + 1
            t_max = math.ceil(y0 / a1) - 1
            if t_min > t_max:
                continue
            cnt = t_max - t_min + 1
            edges.append((i, j, cnt))
    
    # 并查集求连通分量
    dsu = DSU(n)
    for u, v, w in edges:
        dsu.merge(u, v)
    compSize = [0] * n
    for i in range(n):
        compSize[dsu.find(i)] += 1
    maxSize = max(compSize)
    maxComponents = [i for i in range(n) if dsu.find(i) == i and compSize[i] == maxSize]
    
    ans = -1
    # 对每个点数最多的连通块计算 MST
    for comp in maxComponents:
        nodes = [i for i in range(n) if dsu.find(i) == comp]
        inComp = [False] * n
        for u in nodes:
            inComp[u] = True
        compEdges = []
        for u, v, w in edges:
            if inComp[u] and inComp[v]:
                compEdges.append((u, v, w))
        if len(nodes) == 1:
            ans = 0 if ans == -1 else min(ans, 0)
            continue
        compEdges.sort(key=lambda x: x[2])
        dsu2 = DSU(n)
        sum_w = 0
        cnt = 0
        for u, v, w in compEdges:
            ru = dsu2.find(u)
            rv = dsu2.find(v)
            if ru != rv:
                dsu2.merge(ru, rv)
                sum_w += w
                cnt += 1
                if cnt == len(nodes) - 1:
                    break
        if cnt == len(nodes) - 1:
            ans = sum_w if ans == -1 else min(ans, sum_w)
    print(ans)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;
public class Main {
    // 扩展欧几里得算法，求 a*x + b*y = gcd(a, b) 的一组解
    public static long[] extGcd(long a, long b) {
        if(b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] vals = extGcd(b, a % b);
        long d = vals[0];
        long x = vals[2];
        long y = vals[1] - (a / b) * vals[2];
        return new long[]{d, x, y};
    }
    
    // 并查集类
    static class DSU {
        int[] parent;
        public DSU(int n) {
            parent = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
            }
        }
        public int find(int x) {
            if(parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }
        public void merge(int x, int y) {
            int rx = find(x), ry = find(y);
            if(rx != ry)
                parent[ry] = rx;
        }
    }
    
    // 边的类
    static class Edge {
        int u, v;
        long w;
        public Edge(int u, int v, long w) {
            this.u = u; this.v = v; this.w = w;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(parts[0]);
        long k = Long.parseLong(parts[1]);
        parts = br.readLine().trim().split("\\s+");
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(parts[i]);
        }
        ArrayList<Edge> edges = new ArrayList<>();
        // 枚举所有点对
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                long ai = a[i], aj = a[j];
                long d = gcd(ai, aj);
                if(k % d != 0) continue;
                long a1 = ai / d, b1 = aj / d, k1 = k / d;
                // 求特解：a1 * x0 + b1 * y0 = 1
                long[] eg = extGcd(a1, b1);
                long x0 = eg[1] * k1;
                long y0 = eg[2] * k1;
                // 通解： x = x0 + b1 * t, y = y0 - a1 * t, t ∈ ℤ
                // 要求 x > 0 与 y > 0
                // 利用浮点数计算避免整数截断：
                long t_min = (long)Math.floor(- (double)x0 / b1) + 1;
                long t_max = (long)Math.ceil((double)y0 / a1) - 1;
                if(t_min > t_max) continue;
                long cnt = t_max - t_min + 1;
                edges.add(new Edge(i, j, cnt));
            }
        }
        // 用并查集求连通分量
        DSU dsu = new DSU(n);
        for(Edge e : edges) {
            dsu.merge(e.u, e.v);
        }
        int[] compSize = new int[n];
        for(int i = 0; i < n; i++){
            compSize[dsu.find(i)]++;
        }
        int maxSize = 0;
        for(int i = 0; i < n; i++){
            maxSize = Math.max(maxSize, compSize[i]);
        }
        ArrayList<Integer> maxComponents = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(dsu.find(i) == i && compSize[i] == maxSize)
                maxComponents.add(i);
        }
        
        long ans = -1;
        // 对每个点数最多的连通块求最小生成树（Kruskal 算法）
        for(int comp : maxComponents) {
            ArrayList<Integer> nodes = new ArrayList<>();
            for(int i = 0; i < n; i++){
                if(dsu.find(i) == comp)
                    nodes.add(i);
            }
            boolean[] inComp = new boolean[n];
            for(int u : nodes)
                inComp[u] = true;
            ArrayList<Edge> compEdges = new ArrayList<>();
            for(Edge e : edges) {
                if(inComp[e.u] && inComp[e.v])
                    compEdges.add(e);
            }
            if(nodes.size() == 1) {
                ans = (ans == -1 ? 0 : Math.min(ans, 0));
                continue;
            }
            Collections.sort(compEdges, new Comparator<Edge>(){
                public int compare(Edge a, Edge b){
                    return Long.compare(a.w, b.w);
                }
            });
            DSU dsu2 = new DSU(n);
            long sum = 0;
            int cnt = 0;
            for(Edge e : compEdges) {
                int ru = dsu2.find(e.u), rv = dsu2.find(e.v);
                if(ru != rv) {
                    dsu2.merge(ru, rv);
                    sum += e.w;
                    cnt++;
                    if(cnt == nodes.size() - 1)
                        break;
                }
            }
            if(cnt == nodes.size() - 1) {
                if(ans == -1)
                    ans = sum;
                else
                    ans = Math.min(ans, sum);
            }
        }
        System.out.println(ans);
    }
    
    // 求两个数的最大公约数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

题目内容

小美有一个$n$个整数的数组{$a_1,a_2,...,a_n$}和一个整数$k$，他想两两将这些数字连成一张图，规则为:

• 从数组中选取任意两个数字$a_i$和$a_j (i≠j)$，如果$a_i×x+a_j×y=k$存在至少一组正整数解，则将这两个点相连，边权为该方程正整数解的组数;

  连出的图可能由若干个连通块构成，小美只关心那些点数最多的连通块，他想要知道，这些连通块能构成的全部生成树中，权值最小的那棵的权值是多少。

你只需输出这棵生成树的权值。

对于一张$n$个节点的图，选择其中$n-1$条边，使得所有顶点联通，这些边一定会组成一棵树，即为这张图的一棵生成树。可以证明，图中存在至少一棵生成树。

输入描述

第一行输入两个整数$n,k(1≤n≤10^3;1≤k≤10^9)$ 代表小美拥有的数字数量、方程的固定参数。

第二行输入n个整数 $a_1,a_2,...,a_n (1≤ a_i≤ 10^6)$代表小美的数字。

输出描述

在第一行上输出一个整数，代表在点数最多的连通块上，全部生成树中权值最小的那棵的权值。

样例1

输入

5 7
2 3 1 2 7

输出

4

说明

该样例连出的图如下图所示。