zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

\sum_{x=1}^n \sum_{y=1}^n [gcd(x,y)=1][a_{b_x}=b_{a_y}]

可以直接记录v[a_{b_x}]然后统计,用莫比乌斯容斥

#include <bits/stdc++.h>
using namespace std;
#define N 100011
#define ll long long
int a[N],b[N];
int viss[N];
int n;
bool vis[N+10];  
int prime[N+10],mu[N+10];  
int cnt;
void Init(){
    memset(prime,0,sizeof(prime));  
    memset(mu,0,sizeof(mu));  
    memset(vis,0,sizeof(vis));  
    mu[1] = 1;  
    cnt = 0;  
    for(int i=2; i<N; i++){  
        if(!vis[i]){  
            prime[cnt++] = i;  
            mu[i] = -1;  
        }  
        for(int j=0; j<cnt&&i*prime[j]<N; j++){  
            vis[i*prime[j]] = 1;  
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];  
            else{  
                mu[i*prime[j]] = 0;  
                break;  
            }  
        }  
    }
}

ll cal(int x){
    ll res=0;
    for(int i=x;i<=n;i+=x)
        viss[a[b[i]]]++;
    for(int i=x;i<=n;i+=x)
        res+=viss[b[a[i]]];
    for(int i=x;i<=n;i+=x)
        viss[a[b[i]]]--;
    return res;
}
int main(){
    Init();
    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]);
    ll res=0;
    for(int i=1;i<=n;i++)
        res+=1ll*mu[i]*cal(i);
    printf("%lld\n",res );
}
51nod 1675 序列变换
comment评论
Search
search