51Nod 欢乐手速场1 B 序列变换[容斥原理 莫比乌斯函数]

序列变换

alpq654321 (命题人)

 

基准时间限制：1 秒 空间限制：131072 KB 分值: 40

lyk有两序列a和b。

lyk想知道存在多少对x,y，满足以下两个条件。

1：gcd(x,y)=1。

2： a[b[x]] = b[a[y]] 。

 

例如若a={1,1,1}，b={1,1,1}。那么存在7对，因为除了x=2,y=2或x=3,y=3外都满足条件。

Input

第一行一个数n(1<=n<=100000)。
接下来一行n个数，表示ai(1<=ai<=n)。
接下来一行n个数，表示bi(1<=bi<=n)。

Output

一行表示答案

Input示例

3
1 1 1
1 1 1

Output示例

7

---

没有gcd(x,y)=1直接用个桶O(n)统计就好了
然后用到了容斥原理，所有数对(有公因子1)-有1个公因子+有2个不同公因子-有3个不同公因子......
前面的系数就是莫比乌斯函数啊
接下来我们只要计算出x,y都为t的倍数时的答案，再与u[t]相乘累加进答案就可以了。
复杂度O(nlogn),不能用memset哦
PS：为什么有多个p的不算呢？因为这个在一个p时已经算过了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,a[N],b[N];
bool notp[N];
int p[N],mu[N];
void sieve(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!notp[i]) p[++p[0]]=i,mu[i]=-1;
        for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
            notp[i*p[j]]=1;
            if(i%p[j]==0) break;
            mu[i*p[j]]=-mu[i];
        }
    }
}
ll ans=0;
int c[N];
ll calc(int t){
    ll _=0;
    for(int i=t;i<=n;i+=t) c[a[b[i]]]++;
    for(int i=t;i<=n;i+=t) _+=c[b[a[i]]];
    for(int i=t;i<=n;i+=t) c[a[b[i]]]--;
    return _;
}
void solve(){
    for(int i=1;i<=n;i++) if(mu[i]) ans+=calc(i)*mu[i];
    printf("%lld",ans);
}
int main(){
    freopen("in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    sieve(n);
    solve();
}