P7996 [WFOI - 01] 硬币（coin）

你面前有一排 $n$ **堆**硬币排成一线，**同一堆硬币**的面值相同，记第 $i$ 堆硬币的面值为 $a_i$。而**每堆硬币**的数量都相同，记为 $x$。 现在你知道每第 $i$ 堆硬币的面值 $a_i$，你需要确定一个**正整数** $x$，使得**每堆硬币的总金额的**方差最接近于一个**正整数** $k$。 两数 **“最接近”** 的定义：两数之差的绝对值最小。 方差定义：方差 $s ^ 2 = \cfrac{(a_1 - \bar x)^2 + (a_2 - \bar x) ^ 2 + \cdots + (a_n - \bar x) ^ 2}{n}$，其中 $\bar x$ 代表 $x$ 的平均值。

无

无

**【样例 $\#1$ 解释】** 当 $x=3$ 时，第 $i$ 个堆的硬币金额为 $3\times a_i$，这些硬币堆的金额分别为 $21,6,12,18,9,21,30$，可以计算得这些硬币金额的方差约为 $58.78$，可以证明当 $x=3$ 时方差最接近 $47$。 **【样例 $\#2$ 解释】** 可以发现，无论 $x$ 的取值，方差都会为 $0$，所以输出 `No answer!`。 **【数据规模】** **本题采用 Subtask 捆绑测试。** Subtask 编号 | $n,\forall a_i\le$ | $k\le$ | $\footnotesize\texttt{测试点数目}$ | :-: | :-: | :-: | :-: **Subtask #0 $(20\texttt{pts})$** | $10^3$ | $10^9$| $6$ | **Subtask #1 $(25\texttt{pts})$** | $10^5$ | $10^{12}$| $6$ | **Subtask #2 $(25\texttt{pts})$** | $10^5$ | $10^{18}$| $6$ | **Subtask #3 $(30\texttt{pts})$** | $7\times10^6$ | $3\times 10^{18}$| $6$ | 对于 $100\%$ 的数据，$1\le n,\forall a_i\le7\times10^6$，$1\le k\le3\times10^{18}$。记原来 $a$ 数组的方差为 $p$，则数据满足 $p=0$ 或 $p\in[0.25,\ 2^{63}-1]$ 。 **【提示】** 本题读入量较大，请使用合适的读入方式。此处推荐[快速读入模板](https://www.luogu.com.cn/paste/bcfvgxr7)，对于 $\texttt{C/C++}$ 语言，你也可以使用 `scanf` 语句完成读入。 为避免卡精度，建议 `C/C++` 选手使用 $\texttt{double}$ 类型，并不建议使用 `eps`。