[原创]51nod 序列变换 [容斥原理+莫比乌斯函数]【数论+组合数学】

2017-02-10 14:11:00 Tabris_ 阅读数：751

博客爬取于2020-06-14 22:41:44
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54969932

题目连接:http://www.51nod.com/contest/problem.html#!problemId=1675
-------------------------------------------------------------------------------------------------------.
序列变换
alpq654321 (命题人)
基准时间限制：1 秒 空间限制：131072 KB 分值: 40
lyk有两序列a和b。
lyk想知道存在多少对x,y，满足以下两个条件。
1：gcd(x,y)=1。
2： abx = bay 。

例如若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
-------------------------------------------------------------------------------------------------------.

本题是在裸求abx=baya_{b_x} = b_{a_y}的基础上加上了gcd⁡(x,y)=1\gcd(x,y)=1的限制,然后我就不会了,

最后看了题解发现是同容斥原理来解决,
结果来说,
ans[gcd⁡(x,y)=1]−ans[gcd⁡(x,y)!=1]ans[\gcd(x,y)=1]-ans[\gcd(x,y)!=1]

然后就引入了莫比乌斯反演
当x,y均满足题意的时候
f(k) 表示gcd(x,y) == k的个数
F(k) 表示gcd(x,y) == k的倍数 的个数

$f(k)=\sum^{n}_{d=1}μ(d)\times F(d) $

那么系数也就是莫比乌斯函数了

附本题代码
-------------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n;
int prime[N],kp;
int Is_or[N],mu[N];

void Prime(){
    int x;
    mu[1]=1;
    memset(Is_or,true,sizeof(Is_or));
    for(int i=2;i<=n;i++){
        if(Is_or[i]) prime[kp++]=i,mu[i]=-1;
        for(int j=0;j<kp&&i*prime[j]<=n;j++){
            x = i*prime[j];
            Is_or[x]=false;
            if(0==i%prime[j]) break;
            mu[x] = -mu[i];
        }
    }
    return ;
}

int a[N],b[N];
int cnt [N];

LL calc(int t){
    LL ans = 0;
    for(int i=t;i<=n;i+=t) cnt[a[b[i]]]++;
    for(int i=t;i<=n;i+=t) ans+=cnt[b[a[i]]];
    for(int i=t;i<=n;i+=t) cnt[a[b[i]]]--;
    return ans ;
}

int main(){

    n = read();
    Prime();
    Rep(i,1,n) a[i]=read(),cnt[i]=0;
    Rep(i,1,n) b[i]=read();

    LL ans = 0;
    Rep(i,1,n) if(mu[i]) ans += 1ll*calc(i)*mu[i];
    printf("%I64d\n",ans);

    return 0;
}