题目内容

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

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

题解

题目描述

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

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