A16859. Six Seven
编程题
省选/NOI-
知识点
题目描述
对于正整数 $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$。
现在给定一个包含 $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$。
每个测试用例的第一行输入一个整数 $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
-1 5 12 7
说明/提示
在第一个测试用例中，无论如何操作都无法使所有数都变为特殊数。
在第二个测试用例中，进行 $5$ 次操作后，数组变为 $[30,72]$，其中所有元素都是特殊数。
在第四个测试用例中，进行 $7$ 次操作后，数组变为 $[9557358]$。
在第二个测试用例中，进行 $5$ 次操作后，数组变为 $[30,72]$，其中所有元素都是特殊数。
在第四个测试用例中，进行 $7$ 次操作后，数组变为 $[9557358]$。