Permutation Swap
题面翻译
给你一个长度为 \(n\) 的未排序的排列。找到最大的整数 \(k\) 满足可以通过只交换下标差为 \(k\) 的元素使排列被从小到大排序。
题目描述
You are given an unsorted permutation $ p_1, p_2, \ldots, p_n $ . To sort the permutation, you choose a constant $ k $ ( $ k \ge 1 $ ) and do some operations on the permutation. In one operation, you can choose two integers $ i $ , $ j $ ( $ 1 \le j < i \le n $ ) such that $ i - j = k $ , then swap $ p_i $ and $ p_j $ .
What is the maximum value of $ k $ that you can choose to sort the given permutation?
A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2, 3, 1, 5, 4] $ is a permutation, but $ [1, 2, 2] $ is not a permutation ( $ 2 $ appears twice in the array) and $ [1, 3, 4] $ is also not a permutation ( $ n = 3 $ but there is $ 4 $ in the array).
An unsorted permutation $ p $ is a permutation such that there is at least one position $ i $ that satisfies $ p_i \ne i $ .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^{5} $ ) — the length of the permutation $ p $ .
The second line of each test case contains $ n $ distinct integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) — the permutation $ p $ . It is guaranteed that the given numbers form a permutation of length $ n $ and the given permutation is unsorted.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^{5} $ .
输出格式
For each test case, output the maximum value of $ k $ that you can choose to sort the given permutation.
We can show that an answer always exists.
样例 #1
样例输入 #1
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2
样例输出 #1
1
2
3
4
3
2
3
提示
In the first test case, the maximum value of $ k $ you can choose is $ 1 $ . The operations used to sort the permutation are:
- Swap $ p_2 $ and $ p_1 $ ( $ 2 - 1 = 1 $ ) $ \rightarrow $ $ p = [1, 3, 2] $
- Swap $ p_2 $ and $ p_3 $ ( $ 3 - 2 = 1 $ ) $ \rightarrow $ $ p = [1, 2, 3] $
In the second test case, the maximum value of $ k $ you can choose is $ 2 $ . The operations used to sort the permutation are:
- Swap $ p_3 $ and $ p_1 $ ( $ 3 - 1 = 2 $ ) $ \rightarrow $ $ p = [1, 4, 3, 2] $
- Swap $ p_4 $ and $ p_2 $ ( $ 4 - 2 = 2 $ ) $ \rightarrow $ $ p = [1, 2, 3, 4] $
分析
因为数组中元素只有1~n，数字i的初始位置为x，它最后的位置应该要在i(下标从1开始)，也即(x - i) % k == 0，那我们只需要求出每个数的初末位置的差值，然后求所有差值的最大公约数即可，求最大公约数的方法在 最大公约数 有代码和相应说明
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
//求最大公因数
int gcd(int p, int q)
{
return q ? gcd(q, p % q) : p;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i] = abs(a[i] - i); //存需要移动的距离
}
int k = gcd(a[1], a[2]);
for (int i = 3; i <= n; i++)
k = gcd(k, a[i]);
printf(" %d\n", k);
}
}