A. Divisible Array (數(shù)學(xué) + 構(gòu)造)

題意：

構(gòu)造一個(gè)數(shù)列an, 滿足每個(gè) ai % i == 0, 并且對(duì)數(shù)列求和Sn % n == 0。

思路: 先考慮構(gòu)造一個(gè)等差數(shù)列是否滿足條件, 發(fā)現(xiàn)當(dāng) n 為奇數(shù)時(shí), 假如我們將 an 構(gòu)造成:

很顯然對(duì)每一個(gè) i 都有 ai % i == 0, 對(duì)其求和可以發(fā)現(xiàn)

因?yàn)?n 是奇數(shù), 所以 (1 + n) 為偶數(shù)可以被 2 整除, 那么我們一定可以找到一個(gè)整數(shù)??使得?, 所以 Sn 能被 n 整除.

當(dāng) n 為偶數(shù)時(shí), 不難想到將 an 構(gòu)造成:

求和為?, 我們發(fā)現(xiàn)(2 + 2n)一定是偶數(shù), 那么同理我們一定能找到一個(gè)整數(shù)??使得?, 所以?Sn 能被 n 整除.

B. Permutation Swap (最小公倍數(shù))

題意：

給你一個(gè)n位的排列，要求你找到最大的k使得，只交換下標(biāo)差等于k的元素即可將該排列轉(zhuǎn)變成有序的。

思路: 之前做過(guò)一道類似的(記不清了。。。好像是關(guān)于等差數(shù)列的), 我們先看看將所有 Pi 移動(dòng)到正確的位置上時(shí)所需最大值??要滿足怎樣的條件。

不難想到對(duì)于每一個(gè) pi, 移動(dòng)到正確的位置需要? 步, 也就是說(shuō)對(duì)于每一個(gè) , ?必須是? 的倍數(shù)(否則我們不可能構(gòu)造出排列), 那么問(wèn)題就轉(zhuǎn)化為求最大公倍數(shù)了: