2025.12.27 作业 - P12673 「LAOI-8」Change

题目描述

给定一个序列 \(A\) 和一个目标序列 \(B\)，序列中的每个元素互不相同，每次操作可以选定一组 \(i,j\)，满足 \(j-i=k\) 且 \(k\) 为正整数，交换 \(a_i,a_j\)。

保证 \(A\not=B\)，保证经过排序后的 \(A,B\) 相等。

请你求出所有的 \(k\) 使得 \(A\) 可以经过若干次操作变为 \(B\)。

输入格式

第一行一个正整数 \(n\)。
第二行 \(n\) 个整数表示 \(A\)。
第三行 \(n\) 个整数表示 \(B\)。

输出格式

若有 \(m\) 个满足要求的整数 \(k\)，请输出 \(m\) 行，每行一个正整数。

请按照升序输出所有满足要求的 \(k\)。

输入输出样例 #1

输入 #1

5
1 2 3 4 5
1 2 3 5 4

输出 #1

1

输入输出样例 #2

输入 #2

5
1 2 3 5 4
1 3 4 2 5

输出 #2

1

输入输出样例 #3

输入 #3

5
1 4 3 2 5
1 2 3 4 5

输出 #3

1
2

说明/提示

本题采用捆绑测试。

子任务编号	\(n\)	特殊性质	分值
\(1\)	\(\le7\)	无	\(10\)
\(2\)	\(\le2000\)	无	\(20\)
\(3\)	\(\le2\times10^5\)	\(\texttt a\)	\(30\)
\(4\)	\(\le2\times10^5\)	无	\(40\)

特殊性质 \(\texttt a\)：\(A\) 与 \(B\) 仅两个元素位置不同。

对于 \(100\%\) 的数据，满足 \(3\le n\le 2 \times10^5\)，\(1\le A_i,B_i \le 10^9\)。

#include <iostream>
#include <map>
using namespace std;
int n,a[1000005],b[1000005];
map<int,int> w;
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b; a = temp;}return a;
}int main() {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) scanf("%d",&b[i]),w[b[i]]=i;for (int i=1;i<=n;i++) a[i]=w[a[i]];int m=0;for (int i=1;i<=n;i++)b[i]=abs(a[i]-i),m=max(m,b[i]);for (int i=1;i<=n;i++) m=gcd(m,b[i]);for (int i=1;i<=m;i++)if (m%i==0) cout<<i<<endl;return 0;
}