[原创]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;
}