类欧几里得（入门）

# 处理的东西 给定 $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 的博客](https://blog.csdn.net/PoPoQQQ/article/details/46853933)）：  设当前的直线是 $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$） ``` cpp 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$ # 例题 - [\[CROATIAN2010\] ALADIN](https://www.lydsy.com/JudgeOnline/problem.php?id=1938) - [\[BJOI2012\] 算不出的等式](https://www.luogu.org/problemnew/show/P4132) - [poj 3495. Bitwise XOR of Arithmetic Progression](http://poj.org/problem?id=3495) - [loj 6344. 异或和](https://loj.ac/problem/6344) - [bzoj 2987. Earthquake](https://www.lydsy.com/JudgeOnline/problem.php?id=2987) # 题外话 写题解万能模板： > 即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难。 > > 反之亦然同理，推论自然成立，略去过程Q.E.D.，由上可知证毕。 # 更厉害的操作 ~~我可能学了个假的类欧几里得~~ 更加厉害的类欧几里得（真-欧几里得算法） - [fjzzq 类欧几里得算法](https://www.cnblogs.com/zzqsblog/p/8904010.html) - 洪华敦《类欧几里得算法》 ~~当你看完以上内容后，会发现这篇文章可能跟没写似的……~~