类欧几里得（入门）

· · 个人记录

处理的东西

给定 a,b,c,n，求：

\sum_{x=0}^{n-1}\lfloor \frac{ax+b}{c} \rfloor

（要求 a,b,c \gt 0）

换句话说，求直线在某段区间下整点的个数 然后就可以做半平面交内整点个数咯？

核心思想

规约化和旋转坐标轴

具体实现

实际上就是暴力……

规约化

考虑如何化简：

\begin{aligned} &f(a,b,c,n) \\ =&\sum_{x=0}^{n-1}\lfloor \frac{ax+b}{c} \rfloor \\ =&\sum_{x=0}^{n-1}\lfloor \frac{(a \bmod c)x + (a - a \bmod c)x+(b \bmod c)+(b - b \bmod c)}{c} \rfloor \\ =&\sum_{x=0}^{n-1}\lfloor \frac{(a \bmod c)x + (b \bmod c)}{c} \rfloor + \frac{(a - a \bmod c)x}{c} + \frac{b - b \bmod c}{c}\\ =&\sum_{x=0}^{n-1}\lfloor \frac{(a \bmod c)x + (b \bmod c)}{c} \rfloor + \lfloor \frac{a}{c} \rfloor x + \lfloor \frac{b}{c} \rfloor\\ =&\frac{n(n-1)}{2}\lfloor \frac{a}{c} \rfloor + n \lfloor \frac{b}{c} \rfloor + \sum_{x=0}^{n-1}\lfloor \frac{(a \bmod c)x + (b \bmod c)}{c} \rfloor \\ =&\frac{n(n-1)}{2}\lfloor \frac{a}{c} \rfloor + n \lfloor \frac{b}{c} \rfloor + f(a \bmod c,b \bmod c, c, n) \end{aligned}

旋转坐标轴

一副十分熟悉的图（来源：popoqqq 的博客）：

设当前的直线是 y=\frac{ax+b}{c}，旋转后的直线是 \hat y=\frac{\hat ax+\hat b}{\hat c}

处理循环上界

首先假设之前的循环最多枚举到了 n-1，那么变换之后的循环最多到了 \lfloor \frac{an+b}{c} \rfloor - 1

斜率

其次需要明确的是，\frac{a}{c} 和 \frac{\hat a}{\hat c} 表示的是斜率

设 \tan \alpha=\frac{a}{c}，则 \frac{\hat a}{\hat c} = \tan (\frac{\pi}{2}-\alpha)=\frac{1}{tan \alpha}=\frac{c}{a}

截距

之后还需要知道的是，\frac{b}{c} 和 \frac{\hat b}{\hat c} 表示的是纵截距（直线与 y 轴交点的纵坐标）

设 \frac{ax_0+b}{c}=\lfloor \frac{an+b}{c} \rfloor，那么有 x_0=\frac{c \lfloor \frac{an+b}{c} \rfloor - b}{a}

考虑到 (an+b) \bmod c=(an+b)-c \lfloor \frac{an+b}{c} \rfloor，于是有 x_0=\frac{(an+b)-(an+b) \bmod c-b}{a}=n-\frac{(an+b) \bmod c}{a}

同时有：

\frac{\hat b}{\hat c}=n-x_0=\frac{(an+b) \bmod c}{a}

合并方程与特殊解

然后就可以列方程了！！！！！！！！！！！！！

\begin{cases} \frac{\hat a}{\hat c} = \frac{c}{a} \\ \frac{\hat b}{\hat c} = \frac{(an+b) \bmod c}{a} \end{cases}

然后就可以得出一组特殊解：

\begin{cases} \hat a = c \\ \hat b = (an+b) \bmod c\\ \hat c = a \end{cases}

也就是说：

\hat y = \frac{\hat a x + \hat b}{\hat c} = \frac{cx+(an+b)\bmod c}{a}

变换回去

现在目标是变换：

f(a \bmod c,b \bmod c, c, n)=\sum_{i=0}^{n-1}\frac{(a \bmod c)x + b \bmod c}{c}

把变量对应的替换回去后可以得到：

\LARGE \begin{aligned} &f(a \bmod c,b \bmod c, c, n) \\ =&\sum_{i=0}^{\lfloor \frac{a \bmod c \cdot n+b \bmod c}{c} \rfloor - 1}\frac{cx+(a n + b) \bmod c}{a \bmod c} \\ =&f(c,(an+b) \bmod c,a \bmod c, \lfloor \frac{a \bmod c \cdot n+b \bmod c}{c} \rfloor - 1) \end{aligned}

代码

其实代码特别短……

（注意下面这个 f(a,b,c,n) 中的 n 是开区间，也就是说计算的是 \sum_{i=1}^{n-1} \lfloor \frac{ax+b}{c} \rfloor）

ll f(ll a, ll b, ll c, ll n) {
    if(n <= 0) return 0;
    return n * (n - 1) / 2 * (a / c) + n * (b / c) + f(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}

一些奇奇怪怪的套路

取模

a \bmod b=a-b \lfloor \frac{a}{b} \rfloor

异或

计算 f(1) \oplus f(2) \oplus \cdots \oplus f(n) 的话，可以把所有的 f 二进制拆分后再计算

即如果答案的二进制下第 k 位为 1，当且仅当这个式子成立：

\sum_{i=1}^{n}\lfloor \frac{f(i)}{2^k} \rfloor \equiv 1 \pmod {2}

换而言之，涉及位运算的逐位考虑的话，可以直接搞出对应位在模 2 意义下的值，也就是 \lfloor \frac{x}{2^k} \rfloor \bmod 2

例题

题外话

写题解万能模板：

即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难。

反之亦然同理，推论自然成立，略去过程Q.E.D.，由上可知证毕。

更厉害的操作

我可能学了个假的类欧几里得

更加厉害的类欧几里得（真-欧几里得算法）

当你看完以上内容后，会发现这篇文章可能跟没写似的……