【学习笔记】类欧几里得

imily's notebook

2021-02-16

学习笔记, 类欧几里得

平平无奇类欧几里得

最原始的类欧几里得长这样：

$f(a, b, c, n) = \sum\limits_{i = 0}^n \lfloor \frac{ai + b}{c} \rfloor$

其推广形式有

$g(a, b, c, n) = \sum\limits_{i = 0}^n i\lfloor \frac{ai + b}{c} \rfloor$
$h(a, b, c, n) = \sum\limits_{i = 0}^n \lfloor \frac{ai + b}{c} \rfloor ^2$

证明看oi-wiki，这里只复读结论~

设 $m = \lfloor \frac{an + b}{c} \rfloor$

求 $f$

$a \geq c$ 或 $b \geq c$

$f(a, b, c, n) = f(a \% c, b \% c, c, n) + \lfloor \frac{a}{c} \rfloor \frac{n(n + 1)}{2} + \lfloor \frac{b}{c} \rfloor (n + 1)$
$a < c$ 且 $b < c$

$f(a, b, c, n) = nm - f(c, c - b - 1, a, m - 1)$

template

ll euclid(ll n, ll a, ll b, ll c) {
    if (n < 0) return 0;
    if (!a) return (b / c) * (n + 1);
    if (a >= c || b >= c) return n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c) + euclid(n, a % c, b % c, c);
    ll m = (a * n + b) / c;
    return n * m - euclid(m - 1, c, c - b - 1, a);
}

求 $g$

$a \geq c$ 或 $b \geq c$

$g(a, b, c, n) = g(a \% c, b \% c, c, n) + \lfloor \frac{a}{c} \rfloor \frac{n(n + 1)(2n + 1)}{6} + \lfloor \frac{b}{c} \rfloor \frac{n(n + 1)}{2}$
$a < c$ 且 $b < c$

$g(a, b, c, n) = \frac{1}{2}( n(n + 1) m - g(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1) )$

求 $h$

$a \geq c$ 或 $b \geq c$

$h(a, b, c, n) = h(a \% c, b \% c, c, n) + \lfloor \frac{a}{c} \rfloor ^2 \frac{n(n + 1)(2n + 1)}{6} + (n + 1) \lfloor \frac{b}{c} \rfloor ^2 + 2 \lfloor \frac{b}{c} \rfloor f(a \% c, b \% c, c, n) + 2 \lfloor \frac{a}{c} \rfloor g(a \% c, b \% c, c, n) + \lfloor \frac{a}{c} \rfloor \lfloor \frac{b}{c} \rfloor n(n + 1)$
$a < c$ 且 $b < c$

$h(a, b, c, n) = m (m + 1)n + 2g(c, c - b - 1, a, m - 1) - 2f(c, c - b - 1, a, m - 1) - f(a, b, c, n)$

带有下取整的都可以试试类欧几里得。分两种情况：分离后递归，变换后递归。

类欧几里得的最大优势是其几何意义：比如说原始型可理解为一条直线下的整点个数。下面这道在分离那种情况里的几何意义是梯形整点个数。

变换一般也很套路，结合几何意义在坐标轴上旋转/对称/反转… 即可再次转化为可分离的情况。

复杂度 $O(log(\max(a, c)))$。

$Sum$

那个根号在指数上太猖狂了，得想办法把它拿下来。$(-1)^a = 1 - 2 * (a \% 2) = 1 - 2a + 4 \lfloor \frac{a}{2} \rfloor$

我们要求的形如下：$\sum\limits_{d = 1}^n \lfloor d \frac{a \sqrt{r} + b}{c} \rfloor$。

利用类欧几里得的思想，中间那个分数 $\geq 1$ 的时候求的是较短底边长为 $\lfloor \frac{a \sqrt{r} + b}{c} \rfloor$ 的梯形内整点个数，分离并递归；$< 1$ 的时候是个斜边斜率 $< 1$ 的 $Rt△$，把它关于直线 $y = x$ 对称就变成了斜边斜率 $> 1$ 的 $Rt△$。图看其他人的

复杂度考虑每次缩小一半求解区域面积，$O(logn)$。

坑点：long double，gcd 减小分子分母

$Code$

万能欧几里得！

好东西。【感动】

~~复读 START！~~

以最简单的求 $\sum\limits_{x = 1}^n \lfloor \frac{px + r}{q} \rfloor$（这里我们从 $1$ 开始因为下面那道习题就是从 $1$ 开始的 qwq）为例，我们还有一种 $O(T log(\max(p, q)))$ 的算法，其中 $T$ 是两个结构体相乘的复杂度。它适应性很强，可以解决奇形怪状的类欧几里得问题……

画一条直线 $y = \frac{px + r}{q}$，我们有一个路径串，经过横坐标为整点的坐标时丢一个 $R$，经过纵坐标为整点的坐标时丢一个 $U$，都是整点先丢 $U$，用一个结构体表示路径串，$cnt1$、$cnt2$ 分别为 $U$ 和 $R$ 的个数，$sum$ 为答案。路径串拼接过程如下：

$(cnt1, cnt2, sum) \times (cnt1', cnt2', sum')$ $= (cnt1 + cnt1', cnt2 + cnt2', sum + sum' + cnt1 * cnt2')$

没有交换律所以注意顺序。

设 $f(p, q, r, n, U, R)$ 表示计算 $y = \frac{px + r}{q} (x \in [0, n])$，$U$ 和 $R$ 分别为向上和向右的贡献时的答案。$U$ 和 $R$ 初始分别为 $(1, 0, 0)$ 和 $(0, 1, 0)$。规定 $0 \leq r < q$。

$f(p, q, r, n, U, R) =$

$p \geq q$：$f(p \mod q, q, r, n, U, U^{\lfloor \frac{p}{q} \rfloor} R)$
$m = \lfloor \frac{pn + r}{q} \rfloor = 0$：$R^n$
关于 $y = x$ 做对称，把 $U$、$R$ 交换，直线 $y = \frac{px + r}{q}$ 变成 $y = \frac{qx - r}{p}$，到整点时先记 $R$，把直线下移为 $y = \frac{qx - r - 1}{p}$ 就可以先记 $U$ 了；但是 $r’ = -r - 1 \notin [0, p)$，那么先往左后往下平移 $\frac{1}{p}$ 得到 $y = \frac{qx + ((q - r - 1) \mod p)}{p}$。

特判 $(0, 1]$ 和 $(m, \frac{pn + r}{q}]$ 的贡献，返回 $R^{\frac{q - r - 1}{p}} U f(q, p, (q - r - 1) \mod p, m - 1, R, U) R^{n - \frac{q m - r - 1}{p}}$（再说一次不满足交换律！）

细节也没什么了 QwQ，就是初始化一些东西，$U$，$R$ 之类的。

如果从 $0$ 开始，要计入 $0$ 处答案。