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

Tabris

CSDN数学思维组合数学各OJ

发布于：2017年2月10日

次浏览

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

本题是在裸求a_{b_x} = b_{a_y}的基础上加上了 \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;
}

本页文档最后更新于：2021年5月16日

CSDN