A. Divisible Array (数学 + 构造)

题意：

构造一个数列an, 满足每个 ai % i == 0, 并且对数列求和Sn % n == 0。

思路: 先考虑构造一个等差数列是否满足条件, 发现当 n 为奇数时, 假如我们将 an 构造成:

很显然对每一个 i 都有 ai % i == 0, 对其求和可以发现

因为 n 是奇数, 所以 (1 + n) 为偶数可以被 2 整除, 那么我们一定可以找到一个整数  使得 , 所以 Sn 能被 n 整除.

当 n 为偶数时, 不难想到将 an 构造成:

求和为 , 我们发现(2 + 2n)一定是偶数, 那么同理我们一定能找到一个整数  使得 , 所以 Sn 能被 n 整除.

B. Permutation Swap (最小公倍数)

题意：

给你一个n位的排列，要求你找到最大的k使得，只交换下标差等于k的元素即可将该排列转变成有序的。

思路: 之前做过一道类似的(记不清了。。。好像是关于等差数列的), 我们先看看将所有 Pi 移动到正确的位置上时所需最大值  要满足怎样的条件。

不难想到对于每一个 pi, 移动到正确的位置需要  步, 也就是说对于每一个 ,  必须是  的倍数(否则我们不可能构造出排列), 那么问题就转化为求最大公倍数了: