A16859 | $Six Seven$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

对于正整数 $i$ 和 $j$，定义 $f_i(j)$ 为最大的整数 $k$，使得 $i^k$ 能整除 $j$。如果对于某个数 $j$，有 $f_6(j) > f_7(j)$，则称 $j$ 是特殊数。例如，$6$ 是特殊数，但 $67$ 和 $7$ 都不是。 现在给定一个包含 $n$ 个正整数的数组 $a$。你可以进行若干次操作，每次操作将数组的每个元素都加 $1$。 你的任务是找出最少需要多少次操作，才能使数组 $a$ 中所有元素同时变为特殊数。如果无论如何都无法做到，请输出 $-1$。

第一行输入一个整数 $t$，表示测试用例数，$1 \leq t \leq 10^4$。 每个测试用例的第一行输入一个整数 $n$，$1 \leq n \leq 2 \times 10^5$。 每个测试用例的第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$，$1 \leq a_i \leq 10^9$。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示最少操作次数使所有元素都变为特殊数。如果做不到，输出 $-1$。

输入 #1

4
3
1 2 3
2
25 67
8
6 6 12 18 24 36 42 84
1
9557351

输出 #1

C++ 编辑器

输入

输出