[BZOJ1101&BZOJ2301][POI2007]Zap [HAOI2011]Problem b|莫比乌斯反演

时间:2022-09-23 00:18:21

对于给定的整数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|莫比乌斯反演的更多相关文章

  1. &lbrack;POI2007&rsqb;ZAP-Queries &amp&semi;&amp&semi; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    1,[POI2007]ZAP-Queries ---题面---题解: 首先列出式子:$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$ ...

  2. BZOJ2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lbrack;莫比乌斯反演 容斥原理&rsqb;【学习笔记】

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 4032  Solved: 1817[Submit] ...

  3. BZOJ2301&colon; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 然后对于求这样单个的gcd(x,y)=k的, ...

  4. P2522 &lbrack;HAOI2011&rsqb;Problem b &lpar;莫比乌斯反演&rpar;

    题目 P2522 [HAOI2011]Problem b 解析: 具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是,这个题求的是\(\sum_{i=a}^b\sum_{j= ...

  5. Bzoj 2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lpar;莫比乌斯反演&plus;除法分块&rpar;

    2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...

  6. BZOJ 2301&colon; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 1007  Solved: 415[Submit][ ...

  7. BZOJ&period;2301&period;&lbrack;HAOI2011&rsqb;Problem B&lpar;莫比乌斯反演 容斥&rpar;

    [Update] 我好像现在都看不懂我当时在写什么了=-= \(Description\) 求\(\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]\) \(Solution\) 首先 ...

  8. BZOJ 2301 &lbrack;HAOI2011&rsqb;Problem b ——莫比乌斯反演

    分成四块进行计算,这是显而易见的.(雾) 然后考虑计算$\sum_{i=1}^n|sum_{j=1}^m gcd(i,j)=k$ 首先可以把n,m/=k,就变成统计&i<=n,j< ...

  9. 洛谷P2522 &lbrack;HAOI2011&rsqb;Problem b&lpar;莫比乌斯反演&rpar;

    题目描述 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 输入输出格式 输入格式: 第一行一个整数 ...

随机推荐

  1. SQL详解(上)

    SQL 什么是SQL:结构化查询语言(Structured Query Language).SQL标准(例如SQL99,即1999年制定的标准): 由国际标准化组织(ISO)制定的,对DBMS的统一操 ...

  2. Eclipse下新建Maven项目、自动打依赖jar包

    当我们无法从本地仓库找到需要的构件的时候,就会从远程仓库下载构件至本地仓库.一般地,对于每个人来说,书房只有一个,但外面的书店有很多,类似第,对于Maven来说,每个用户只有一个本地仓库,但可以配置访 ...

  3. Windows Azure 安全最佳实践 - 第 2 部分:Azure 提供哪些现成可用的安全机制

    在WindowsAzure安全最佳实践 - 部分:深度解析挑战防御对策中,我介绍了威胁形势以及在您的应用程序中采用深度防御的计划. 在本部分中,我将说明 Windows Azure的安全是一项共同责任 ...

  4. skynet源代码学习 - 从全局队列中弹出&sol;压入一个消息队列过程

    学习云风的skynet源代码,简单记录下. void skynet_globalmq_push(struct message_queue * queue) { struct global_queue ...

  5. Vue&plus;Webpack构建去哪儿APP&lowbar;一&period;开发前准备

    一.开发前准备 1.node环境搭建 去node.js官网下载长期支持版本的node,采用全局安装,安装方式自行百度 网址:https://nodejs.org/zh-cn/ 安装后在cmd命令行运行 ...

  6. Linux中,去掉终端显示的当前目录的绝对路径

    Linux中,去掉终端显示的当前目录的绝对路径 去~/.bashrc中,找到PS1变量的定义,如果没有,手动加上: 可以将显示输出到标题栏上: #export PS1="[e]2;u@H w ...

  7. 翻译下 golang package time

    # 关于 `package time` 个人体会:"wall clock" 可以理解为就是实际的时钟,而 "monotonic clock" 则是程序内部的时钟 ...

  8. 使用k8s cronjob &comma;清除应用生成的日志文件

    目前应用日志,tomcat日志 统一输出到 /data/logs/pod名字/ 目录下,并且/data/logs 目录挂载到cephfs上, tomcat 日志使用 cronolog进行日志切割 使用 ...

  9. vue引用样式

    cnpm i sass-loader node-sass -D <link rel="stylesheet" href="./static/reset.css&qu ...

  10. &lbrack;Node&period;js&rsqb; Show More Lines in a Node&period;js Error Stack Trace

    Sometimes you are one or two lines short from finding the cause of the error in the stack trace but ...