「LAOI-8」Change 题解

Anemones · 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;
}