Stern-Brocot Tree、伪.GCD 副本

Stern-Brocot Tree、伪.GCD 副本

伪.GCD

问题 1：(f(a,b,c,n) = sum_{i=0}^{n} [frac{ai+b}{c}])

• Case 1: (ageq c 或 bgeq 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} - qsum_{i=1}^{n}[frac{pi}{q}])

Rikka with Ants

做法

• 对于直线 (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}])

KM and M

做法

• 逐位考虑，考虑第 (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}})

WifiPlanet

太难了

• 把多边形剖成若干个梯形。
• 不会剖简单多边形，被搞得自闭了。

probedroids

做法

• 用「伪.gcd」check 答案
• SB 树上二分即可。

HDU6624: fraction

题意

给 (x,p) 求极小的 (a) 使得 (ax\%p<a)

做法

• 只需寻找最小的 (k)，使得 (kp leq ax<kp+a)。
• (frac{p}{x} leq frac{a}{k} < frac{p}{x-1})。