Stern-Brocot Tree、伪.GCD 副本
2024-10-07 21:40:25
Stern-Brocot Tree、伪.GCD 副本
伪.GCD
问题 1:\(f(a,b,c,n) = \sum_{i=0}^{n} [\frac{ai+b}{c}]\)
- Case 1: \(a\geq c 或 b\geq c\):\(f(a,b,c,n) = f(a\%c,b\%c,c,n)+(n+1)[\frac{b}{c}] + \frac{n(n+1)}{2}[\frac{a}{c}]\)
- Case 2: 令 \(m=[\frac{an+b}{c}]\), 有 $f(a,b,c,n) = \sum_{i=0}^{n}\sum_{j=1}^{m}[[\frac{ai+b}{c}] \geq j] = \sum_{i=0}^{n}\sum_{j=0}^{m-1}[[\frac{ai+b}{c}] \geq j+1] = $
- \(= \sum_{i=0}^{n}\sum_{j=0}^{m-1}[ai > cj+c-b-1]=\sum_{i=0}^{n}\sum_{j=0}^{m-1} m - [\frac{cj+c-b-1}{a}]\)
- \(= nm - f(c,c-b-1,a,m-1)\)
问题 2:求 \(\frac{a}{b}<\frac{x}{y}<\frac{c}{d}\),的最小正整数解 \(y\).
- Case 1:
Stern-Brocot Tree
提问:xxxxxx 问题的答案是 \(\frac{p}{q}\) (\(p \leq 10^6, q \leq 10^5\)),怎么二分?
我觉得我可以二分一个实数 ........ 然后 ....... 睡觉。
做法 solve(a,b,c,d)
在 \([\frac{a}{b},\frac{c}{d}]\) 中寻找答案。
- check 一下 \(\frac{a+c}{b+d}\)。
- 小了的话,沿着 SB 树向右下方突突突。二分求出极小的 \(k\),使得 \(\frac{a+kc}{b+kd}\) 大于等于正确答案。
solve(a,b,a+kc,b+kd)
- 大了的话,沿着 SB 树向右下方突突突。二分求出极小的 \(k\),使得 \(\frac{ka+c}{kb+d}\) 小于等于正确答案。
solve(ka+c,kb+d,c,d)
- 二分次数是 log 级别的,不会证明。
练习
It's a Mod, Mod, Mod, Mod World
做法
- \(\sum_{i=1}^{n} pi\%q = \sum_{i=1}^{n}(pi-q[\frac{pi}{q}]) = \frac{pn(n+1)}{2} - q\sum_{i=1}^{n}[\frac{pi}{q}]\)
做法
- 对于直线 \(y=\frac{a}{b}x\),点 \((x,y)\) 在路径上,那么 \(\frac{y}{x} \leq \frac{a}{b}, \frac{y+1}{x-1}>\frac{a}{b}\)
化简一下 \(\frac{a(x-1) - b}{b}< y \leq \frac{ax}{b}\) - 不妨设 \(\frac{a}{b}<\frac{c}{d}\),那么有 \(\frac{c(x-1)-d}{d} <y \leq \frac{ax}{b}\)
- \(ans=\sum_{x=1}^{n} [\frac{ax}{b}] - \sum_{x=1}^{n}[\frac{cx-(c+d)}{d}]\)
做法
- 逐位考虑,考虑第 \(b\) 位,我们想知道多少个 \(k\) 使得 \(km\) 在这位上为 1,即 \(km\%(2^b) \geq 2^{b-1}\)。
- \(ans = \frac{[\sum{km\%2^b}] - [\sum km\%2^{b-1}]}{2^{b-1}}\)
太难了
- 把多边形剖成若干个梯形。
- 不会剖简单多边形,被搞得自闭了。
做法
- 用「伪.gcd」check 答案
- SB 树上二分即可。
题意
给 \(x,p\) 求极小的 \(a\) 使得 \(ax\%p<a\)
做法
- 只需寻找最小的 \(k\),使得 \(kp \leq ax<kp+a\)。
- \(\frac{p}{x} \leq \frac{a}{k} < \frac{p}{x-1}\)。
最新文章
- Android实现TCP断点上传,后台C#服务实现接收
- JavaScript高级程序设计学习笔记--BOM
- VMware12 安装 CentOS 6.5 64位
- Openstack Murano(kilo)二次开发之添加Volume
- BestCoder12 1001.So easy(hdu 5058) 解题报告
- cojs 自己出的题目 解题报告
- why dicePlayer cannot player with defy mb526
- 不改变中间层,如何玩转 .NET 的远程处理功能?
- mysql出现Got error 28 from storage engine错误
- SKTextureAtlas类
- 在C#、Java中,为什么不能用[返回值]区别重载方法?
- Team Queue(多队列技巧处理)
- SQL server 2008无法连接Local服务器的解决办法
- log4j的使用及参考
- 【iOS开发-22】navigationBar导航栏,navigationItem建立:获取导航栏中的基本文本和button以及各种跳跃
- Hybrid
- 【安装Python环境】之“安装 setuptools ”时出现的问题以及解决办法
- python打开一个本地目录文件路径
- .Net学习计划
- String对象常量池特性对synchronized对象的影响