[原创]51nod 序列变换 [容斥原理+莫比乌斯函数]【数论+组合数学】
[原创]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
-------------------------------------------------------------------------------------------------------.
本题是在裸求的基础上加上了的限制,然后我就不会了,
最后看了题解发现是同容斥原理来解决,
结果来说,
然后就引入了莫比乌斯反演
当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 | int n; |