数论卷积公式and莫比乌斯反演
数论卷积:
对于两个数论函数f(x),g(x)
f(n)g(n)=∑ f(d)g(n/d)
d|n
莫比乌斯函数:
设一个数n=(p1^k1)*(p2^k2)*(p3^k3)*..........*(pn^kn)
/ 1,n=1
则μ(n)= 0,max(k1,...kn)=1
\ -1^r ,max(k1......kn)=r,r>1
莫比乌斯函数有个性质:
∑ μ(d)在n为1时为1,其余时为0
d|n
例题:给定a,b,c,d,在a≤x≤c,b≤y≤d中,求满足gcd(x,y)=1的(x,y)
这样,我们就可以把要求的x,y视为一个二维前缀和,即:
[1≤x≤c,1≤y≤d]-[1≤x≤a,1≤y≤d]-[1≤x≤c,1≤y≤b]+[1≤x≤a,1≤y≤b](就是上图红色部分的面积=总面积-a*d的矩形-c*b的矩形+a*b的矩形)
那么每一部分就可以表示为求起点为1,x的终点为n,y的终点为m的式子
如下:
n m
∑ ∑ [gcd(i,j)]=1
i=1 j=1
这里中括号的意思是:若括号内为真,返回1,若为假,返回0
∑计算有一下几种性质:
1.交换两个∑,结果不变
2.将某个∑后面与当前∑枚举的东西无关的式子提到该∑前面来,结果不变
显然枚举原式可以枚举到地老天荒(显然我们要化简)
联系一下前面莫比乌斯函数的性质:
∑ μ(d)在n为1时为1,其余时为0
d|n
不难发现,原式可以写成这样:
显然这里确定i,j枚举d不好枚举,那我们换过来,确定d枚举i,j
n
∑ ∑ ∑ μ(d)
d=1 ad=i, bd=j,
i<=n j<=m
这时候,μ(d)与前两个∑没有关系,那就把它提到前面来
n
∑ μ(d) ∑ ∑
d=1 ad=i, bd=j,
i<=n j<=m
后面两个∑可视为枚举1到n和1到m中d的倍数。1到n中d的倍数有 个,1到m中d的倍数有 个
一个式子解决了。
剩下的就是将二维前缀和中的式子往里带了
嗯虽然不知道自己写了些什么,但先记下来以后慢慢看
最新文章
- Azure ARM (11) ARM模式下,创建虚拟机并配置负载均衡器
- iOS 含有 中文的URL 转码问题
- 实际项目中积累的一些关于事件的简单应用JS代码段(能力有限,不喜轻喷,23333)
- mysql及redis环境部署时遇到的问题解决
- BZOJ1747 [Usaco2005 open]Expedition 探险
- highchart.js的使用
- wordpress学习-themes-001
- Photoshop/PS中如何写维吾尔语等语言 乱码
- 16进制字符串转数字(C/C++,VB/VB.net,C#)
- A Tour of Go If
- 《SDN核心技术剖析和实战指南》2.1交换机核心技术小结
- 简单的CSS 下拉导航菜单实现代码
- sql server 深入使用 总结 part1
- 京香julia_百度百科
- 图文:eclipse中SVN分支合并到主干
- java怎么连接mysql数据库
- SiganlR 系列之概述
- OpenStack实践系列⑨云硬盘服务Cinder
- HDU3339 In Action 【最短路】+【01背包】
- Mybatis缓存(1)--------系统缓存及简单配置介绍
热门文章
- jQuery 省份选择
- c++中的c_str()用法
- Fedora 23+CUDA 8.0+ GTX970 安装
- Java程序员从阿里拿到offer回来,这些面试题你会吗?
- ORA-12638: 身份证明检索失败的解决方法
- request.getRealPath的替代方法
- mysql数据库基础语句训练题
- centos7下stf安装介绍(一)----环境搭建
- mysql 在 win 安装 最全攻略(附转载的乱码终极解决方案)以及解决data too long for column &#39;name&#39; at row 1, 一种可能就是因为编码一致性问题.
- OperateResult 基础类及派生类介绍