题解

题目描述

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

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

题目内容

小美有一个$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

说明

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