这里只是类欧几里得的一种:
快速求下式:
$$f(a, b, c, n) = \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor$$

其中 a, b, c, n 都是正整数。

缩小 a, b 规模

首先的目标是让 a, b 小于 c 。

结论 1 :
$$\lfloor \frac{Ax+B}{y} \rfloor =
\lfloor \frac{A(x\%y)+B}{y} \rfloor + A\lfloor \frac{x}{y} \rfloor$$

证明:
首先用到整除与取模的转换:
$\lfloor \frac{x}{y} \rfloor = \frac{x-x\%y}{y}$ 。
得到原命题等价于:
$$\frac{Ax+B-(Ax+B)\%y}{y} =
\frac{A(x\%y)+B-(A(x\%y)+B)\%y}{y} + A\frac{x-x\%y}{y}$$
$$Ax + B – (Ax+B)\%y = A(x\%y) + B – (A(x\%y)+B)\%y + A(x-x\%y)$$
$$Ax – (Ax+B)\%y = A(x\%y) – (A(x\%y)+B)\%y + A(x-x\%y)$$
$$Ax – (Ax+B)\%y = A(x\%y) – (Ax+B)\%y + A(x-x\%y)$$
$$Ax = A(x\%y) + A(x-x\%y)$$
$$Ax = A(x\%y) + Ax – A(x\%y)$$
得证。

那么通过这个结论可以得知:
$$
\begin{equation}
\begin{aligned}
f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\
&= \sum_{i=0}^n (\lfloor \frac{(a\%c)i+b\%c}{c} \rfloor +
i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\
&= f(a\%c, b\%c, c, n) + \sum_{i=0}^n (
i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\
\end{aligned}
\end{equation}
$$

后面那一段就是一个等差数列求和,于是 a, b 被转换为小于 c 。

转换成子问题减小规模

整除除了用取模代替外,还有一种方法。

结论 2 :
$$\lfloor \frac{x}{y} \rfloor = \sum_{i=1}^{MAX} [i \leq \frac{x}{y}]$$
其中 MAX 是任意一个足够大的值。
证明?相当于从 1 开始数,感性理解即可。

那么通过这个结论可以得知:
$$
\begin{equation}
\begin{aligned}
f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\
&= \sum_{i=0}^n \sum_{j=1}^{(an+b)/c} [j \leq \frac{ai+b}{c}] \\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [j + 1 \leq \frac{ai+b}{c}] \\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c \leq ai+b] \\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c – 1 < ai+b] \\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [\frac{cj+c-b-1}{a} < i] \\
&= \sum_{j=0}^{(an+b)/c-1} \sum_{i=0}^n [\frac{cj+c-b-1}{a} < i] \\
&= \sum_{j=0}^{(an+b)/c-1}
(n + 1 – \sum_{i=0}^n [i \leq \frac{cj+c-b-1}{a}]) \\
&= \sum_{j=0}^{(an+b)/c-1}
(n – \lfloor \frac{cj+c-b-1}{a} \rfloor) \\
&= n \lfloor \frac{an+b}{c} \rfloor –
\sum_{j=0}^{(an+b)/c-1} (\lfloor \frac{cj+c-b-1}{a} \rfloor) \\
&= n \lfloor \frac{an+b}{c} \rfloor – f(c, c-b-1, a, (an+b)/c-1)
\end{aligned}
\end{equation}
$$

那么就得到了一个递归计算 f(a, b, c, n) 的算法,
a = 0 时上式不成立,因为上面的推导有除以 a 的步骤。
因此将 a = 0 作为终止状态,此时 f 的计算是常数数列求和。
复杂度是对数复杂度 log(a),因为上面的过程规模的减小速度相当于 gcd 。


3 条评论

sys_con · 2019年7月3日 下午8:05

想水一发的是其实”那题”不用类欧直接用性质暴力搞也能过 (逃

    Kewth · 2019年7月3日 下午9:37

    我人丑常数大,卡常死活过不了。。。

      sys_con · 2019年7月11日 下午7:39

      可能是写的方式不对

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: