自动搬运

查看原文

来自洛谷，原作者为

	Anemones 欢迎加群 638399574

搬运于2025-08-24 23:17:18，当前版本为作者最后更新于2024-09-16 16:37:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易发现 $A,B$ 中的相同元素的距离为 $t$ 时，当且仅当 $k$ 为 $t$ 的因数时 $A$ 中的这个元素才能移动到 $B$ 的位置。

所以对于每个元素的相对距离取最大公约数，然后求一下所有因数即可。

特判距离为 $0$。

//luogu uid:Anemones 736184
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char c=getchar(),f=0;int t=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
    return f?-t:t;
}
inline void write(int x){
    static int t[25];int tp=0;
    if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
    while(x) t[tp++]=x%10,x/=10;
    while(tp--) putchar(t[tp]+48);
}
struct node{
    int x,id;
};
int n;
int a[200009],b[200009];
node qaq[200009];
bool cmp(const node &x,const node &y){
    return x.x<y.x;
}
int get(int temp){
    int l=1,r=n;
    while(l<=r){
        int mid=l+r>>1;
        if(temp==qaq[mid].x) return qaq[mid].id;
        else if(temp<qaq[mid].x) r=mid-1;
        else l=mid+1;
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
    	a[i]=read();
        qaq[i]={a[i],i};
    }
    sort(qaq+1,qaq+n+1,cmp);
    for(int i=1;i<=n;i++){
        int bi=read();
        b[i]=abs(i-get(bi));
    }
    sort(b+1,b+n+1,greater<int>());
    int ans=b[1];
    for(int i=2;i<=n;i++){
        if(!b[i]) break;
        ans=__gcd(ans,b[i]);
    }
    if(!b[1]){
        for(int i=1;i<=n;i++){
            write(i),putchar('\n');
        }
    }
    else{
        for(int i=1;i<=n;i++){
            if(ans%i==0) write(i),putchar('\n');
        }
    }
    return 0;
}