526互联

Codeforces Round 873 (Div. 2) B. Permutation Swap

发布时间 2023-09-05 21:22:53作者: zsxuan

给一个无序排列 \(p_1, p_2, \cdots, p_n\) 。为了排序这个排列，选一个常数 \(k(k \geq 1)\) 并且在排列上做一些操作。

  • 一次操作可以选择 \(i, j, (1 \leq j < i \leq n),\ s.t.\ j - i = k\) ，然后执行 \(swap(p_i, p_j)\) 。

询问最大可选择的 \(k\) ，能够保证排序这个排列。

考虑一个显然的典。

操作次数不限，当 \(k\) 确定，则可以保证下标为 \(x \equiv x_0 (\mod k)\) \((1 \leq x_0 \leq k - 1)\) 的数任意置换。

另一个关键是，考虑排列的性质。（cf 的思维题也喜欢考察排列性质）

无序排列变为有序时，具有性质：

  • \(\forall i, id = i\) 的数，最终落在 \(id = p_i\) 的位置。

观察：对于无序排列某个 \(i\) ，能够回序的条件为 \(k\ \mid\ |p_i - i|\) 。

问题变为一个经典的数论题。有关一个数连续整除一段数。

  • 最大的 \(k\) 满足 \(k \mid c_i\) 即 \(gcd(c_1, c_2, \cdots, c_n)\) ，此处 \(c_i = |p_i - i|\) 。
view 
#include <bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	ll g = 0;
	for (int i = 1; i <= n; i++) g = gcd(g, abs(a[i] - i));
	std::cout << g << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}