对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。
我们可以令F[n]=使得n|(x,y)的数对(x,y)个数
这个很容易得到,只需要让x,y中都有n这个因子就好了,也就是[a/n]*[b/n]个数对(向下取整)
然后设题中所要求的为f[n],很容易得知,F[n]=∑f[d](n|d)
莫比乌斯反演可以得到f[n]=∑μ(d/n)F[d](n|d)
这样是O(n),然而数据范围5*10^4显然不能通过
f[n]=∑μ(d/n)[a/d][b/d](n|d)
这个式子停止的条件是a/d=0或者b/d=0
令m=min(a/n,b/n)
f[n]=∑μ(i)[a/(i*n)][b/(i*n)](1<=i<=m)
然后可以通过一些方法证明[a/(i*n)] = [[a/i]/n]
毕竟弱.证明得这么差..
证明:[n/(a*b)]=[[n/a]/b]
设[n/a]=(n-x)/a (x<a)
设[[n/a]/b]=((n-x)/a-y)/b (y<b)
[[n/a]/b]=(n-x-ay)/ab,设[n/(a*b)]=(n-e)/ab
设二者不等,即(n-x-ay)/ab+t=(n-e)/ab(t>=1)
x+ay=e+tab
x-e=a(tb-y)
∵a>0,b>y ∴a(tb-y)>0
而x是n/a的余数,e是n/ab的余数,显然e>=x,x-e<=0,矛盾
所以[a/(i*n)] = [[a/i]/n]
然后直接枚举每一个可能的[a/(i*n)][b/(i*n)]的取值就好了
莫比乌斯函数用前缀和累计
BZOJ1101交了22发...创了个人记录啊..
Pas错误不明..后来改用C++,是因为!i mod prime[j]这里没有加括号..用==0就不会错了...
BZOJ2301
容斥将一个问题拆分成四个子问题即可
[BZOJ1101&BZOJ2301][POI2007]Zap [HAOI2011]Problem b|莫比乌斯反演的更多相关文章
-
[POI2007]ZAP-Queries &;&; [HAOI2011]Problem b 莫比乌斯反演
1,[POI2007]ZAP-Queries ---题面---题解: 首先列出式子:$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$ ...
-
BZOJ2301: [HAOI2011]Problem b[莫比乌斯反演 容斥原理]【学习笔记】
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MBSubmit: 4032 Solved: 1817[Submit] ...
-
BZOJ2301: [HAOI2011]Problem b 莫比乌斯反演
分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 然后对于求这样单个的gcd(x,y)=k的, ...
-
P2522 [HAOI2011]Problem b (莫比乌斯反演)
题目 P2522 [HAOI2011]Problem b 解析: 具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是,这个题求的是\(\sum_{i=a}^b\sum_{j= ...
-
Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...
-
BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MBSubmit: 1007 Solved: 415[Submit][ ...
-
BZOJ.2301.[HAOI2011]Problem B(莫比乌斯反演 容斥)
[Update] 我好像现在都看不懂我当时在写什么了=-= \(Description\) 求\(\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]\) \(Solution\) 首先 ...
-
BZOJ 2301 [HAOI2011]Problem b ——莫比乌斯反演
分成四块进行计算,这是显而易见的.(雾) 然后考虑计算$\sum_{i=1}^n|sum_{j=1}^m gcd(i,j)=k$ 首先可以把n,m/=k,就变成统计&i<=n,j< ...
-
洛谷P2522 [HAOI2011]Problem b(莫比乌斯反演)
题目描述 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 输入输出格式 输入格式: 第一行一个整数 ...
随机推荐
-
SQL详解(上)
SQL 什么是SQL:结构化查询语言(Structured Query Language).SQL标准(例如SQL99,即1999年制定的标准): 由国际标准化组织(ISO)制定的,对DBMS的统一操 ...
-
Eclipse下新建Maven项目、自动打依赖jar包
当我们无法从本地仓库找到需要的构件的时候,就会从远程仓库下载构件至本地仓库.一般地,对于每个人来说,书房只有一个,但外面的书店有很多,类似第,对于Maven来说,每个用户只有一个本地仓库,但可以配置访 ...
-
Windows Azure 安全最佳实践 - 第 2 部分:Azure 提供哪些现成可用的安全机制
在WindowsAzure安全最佳实践 - 部分:深度解析挑战防御对策中,我介绍了威胁形势以及在您的应用程序中采用深度防御的计划. 在本部分中,我将说明 Windows Azure的安全是一项共同责任 ...
-
skynet源代码学习 - 从全局队列中弹出/压入一个消息队列过程
学习云风的skynet源代码,简单记录下. void skynet_globalmq_push(struct message_queue * queue) { struct global_queue ...
-
Vue+Webpack构建去哪儿APP_一.开发前准备
一.开发前准备 1.node环境搭建 去node.js官网下载长期支持版本的node,采用全局安装,安装方式自行百度 网址:https://nodejs.org/zh-cn/ 安装后在cmd命令行运行 ...
-
Linux中,去掉终端显示的当前目录的绝对路径
Linux中,去掉终端显示的当前目录的绝对路径 去~/.bashrc中,找到PS1变量的定义,如果没有,手动加上: 可以将显示输出到标题栏上: #export PS1="[e]2;u@H w ...
-
翻译下 golang package time
# 关于 `package time` 个人体会:"wall clock" 可以理解为就是实际的时钟,而 "monotonic clock" 则是程序内部的时钟 ...
-
使用k8s cronjob ,清除应用生成的日志文件
目前应用日志,tomcat日志 统一输出到 /data/logs/pod名字/ 目录下,并且/data/logs 目录挂载到cephfs上, tomcat 日志使用 cronolog进行日志切割 使用 ...
-
vue引用样式
cnpm i sass-loader node-sass -D <link rel="stylesheet" href="./static/reset.css&qu ...
-
[Node.js] Show More Lines in a Node.js Error Stack Trace
Sometimes you are one or two lines short from finding the cause of the error in the stack trace but ...