Squaring | Serendipity

type

status

date

slug

summary

题目描述

ikrpprpp 发现了一个由整数组成的数组。他喜欢公平，所以想让变得公平，也就是让它不递减

为此，他可以对数组中的索引进行公正操作，将替换为（位置的元素及其平方）。例如，如果，ikrpprpp 选择对执行正义行动，那么就会变成。

要使数组不递减，最少需要多少次正义行动？

第一行包含一个整数 - 测试用例的数量。随后是测试用例的描述。

对于每个测试用例，第一行包含一个整数 - 数组的大小。第二行包含个整数。

所有测试用例中的总和不超过。

对于每个测试用例，打印一个整数--使数组不递减所需的最小正义行为数。如果无法做到，则打印。

在第一个测试案例中，无需执行正义行为。阵列本身就是公平的！

在第三个测试案例中，可以证明数组不可能非递减。

在第五个测试用例中，ikrpprppp 可以在索引上执行一次正义行动，然后在索引上执行一次正义行动，最后在索引上执行另一次正义行动。之后，将变成。

观察数据范围，我们可以暴力求解次数。但是这样会面临一个问题，爆long long而导致答案错误。

我们先来观察相邻的两个数。我们假定是两个相邻的数，如果，我们需要对操作。假设是数组的第一个元素，我们只需要找到一个，使得。那么如果并不是数组的第一个元素呢，我们假设到时要满足条件需要进行了次操作，即，此时，由于幂函数的单调性可知依然成立。也就是说到时，需要操作次。

所以，我们只需要遍历数组，记录下前个数时的操作次数，即可得到第个数的操作次数，然后累加即可。

下面是 ac 代码：