CF1216D Swords

剧院地下室里曾经存放着 $n$ 种类型的剑，每种类型的剑恰好有 $x$ 把。有 $y$ 个人闯入了剧院地下室，每个人恰好拿走了某一种类型的 $z$ 把剑。注意，不同的人可以选择不同类型的剑。你并不知道 $x$、$y$ 和 $z$ 的具体数值。 第二天早上，剧院导演发现了失窃事件。他清点了所有的剑——第 $i$ 种类型的剑还剩下 $a_i$ 把未被动过。 导演对地下室最初每种类型的剑的数量、闯入地下室的人数以及每个人拿走的剑的数量都一无所知。 例如，如果 $n=3$，$a=[3, 12, 6]$，那么其中一种可能的情况是 $x=12$，$y=5$，$z=3$。此时，前三个人拿走了第一种类型的剑，每人 $3$ 把，另外两个人拿走了第三种类型的剑，每人 $3$ 把。注意，你事先并不知道 $x$、$y$ 和 $z$ 的值，但你知道 $n$ 和 $a$ 的值。 因此，他请求你的帮助。请你确定可能闯入地下室的最少人数 $y$，以及每个人拿走的剑的数量 $z$。

输入的第一行包含一个整数 $n$ $(2 \le n \le 2 \cdot 10^{5})$，表示剑的类型数。 输入的第二行包含一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^{9})$，其中 $a_i$ 表示失窃后第 $i$ 种类型的剑还剩下的数量。保证至少存在一对下标 $(j, k)$ 使得 $a_j \neq a_k$。

输出两个整数 $y$ 和 $z$，分别表示可能闯入地下室的最少人数，以及每个人拿走的剑的数量。

在第一个样例中，最小的 $y$ 等于 $5$，即可能闯入地下室的最少人数为 $5$。每个人拿走了 $3$ 把剑：其中三个人各自拿走了第一种类型的 $3$ 把剑，另外两个人各自拿走了第三种类型的 $3$ 把剑。 在第二个样例中，最小的 $y$ 为 $1$，即可能闯入地下室的最少人数为 $1$。他拿走了第一种类型的 $7$ 把剑。 由 ChatGPT 4.1 翻译