给你一个未经排序的排列组合p1,p2,...,pn。为了对这个排列组合进行排序，你选择一个常数k（k≥1）并对排列组合进行一些操作。在一个操作中，你可以选择两个整数i，j（1≤j<i≤n），使i-j=k，然后交换pi和pj.
你可以选择多大的k值来对给定的排列进行排序？
一个排列组合是一个由1到n的n个不同的整数按任意顺序组成的数组。例如，[2,3,1,5,4]是一个排列组合，但是[1,2,2]不是排列组合（2在数组中出现两次），[1,3,4]也不是排列组合（n=3，但是数组中有4但数组中却有4个）。
一个未排序的排列组合p是一个排列组合，它至少有一个位置i满足pi≠i。
2903: 排列式交换（思维+数学）
时间限制: 1 Sec 内存限制: 256 MB提交: 0 解决: 2
[提交][状态][讨论版][命题人:]
题目描述
输入描述
每个测试包含多个测试用例。
第一行包含测试用例的数量t（1≤t≤104).测试用例的描述如下。
每个测试用例的第一行包含一个单一的整数n（2≤n≤105）-- permutation的长度p.
每个测试案例的第二行包含n个不同的整数p1,p2,...,pn(1≤pi≤n)它保证给定的数字形成长度为n的排列并且所给的排列组合是未排序的。
保证所有测试案例的n之和不超过2⋅105。
第一行包含测试用例的数量t（1≤t≤104).测试用例的描述如下。
每个测试用例的第一行包含一个单一的整数n（2≤n≤105）-- permutation的长度p.
每个测试案例的第二行包含n个不同的整数p1,p2,...,pn(1≤pi≤n)它保证给定的数字形成长度为n的排列并且所给的排列组合是未排序的。
保证所有测试案例的n之和不超过2⋅105。
输出描述
对于每个测试案例，输出你可以选择的最大的k的最大值来对给定的排列组合进行排序。
我们可以证明，答案总是存在的。
我们可以证明，答案总是存在的。
样例输入
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
2
3
4
3
2
3
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 5125
关于网站改版