类欧几里得算法-学习笔记

## 有用的结论 $$a \le \lfloor\frac{b}{c}\rfloor \Leftrightarrow ac\le b$$ $$a\ge \lceil\frac{b}{c}\rceil \Leftrightarrow ac\ge b$$ $$a\lt \lceil\frac{b}{c}\rceil \Leftrightarrow ac\lt b$$ $$a\gt \lfloor\frac{b}{c}\rfloor \Leftrightarrow ac\gt b$$ 记住有等号则符号和大小与号一致，否则相反即可。 $$\lfloor\frac{b}{c}\rfloor = \lceil \frac{b-c+1}{c}\rceil$$ $$\lceil \frac{b}{c}\rceil = \lfloor\frac{b+c-1}{c}\rfloor$$ 可以和上面几个等价关系一起用。 ## 正文 我们要计算 $$f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$$ 首先，我们解决一个小问题： ### $a\ge c$ or $b\ge c$ 两个性质： $$\lfloor r+n\rfloor=\lfloor r\rfloor+n,r\in R,n\in N$$ $$\lfloor\frac{ax}{b}\rfloor=\lfloor\frac{(a\bmod b)x}{b}\rfloor+x\lfloor\frac{a}{b}\rfloor $$ 于是可得： $$\lfloor\frac{ai+b}{c}\rfloor=\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+i\lfloor\frac{a}{c}\rfloor +\lfloor\frac{b}{c}\rfloor$$ 那么我们把它放进求和号： $$f(a,b,c,n)=f(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor$$ 问题解决了！ ### 递归地解决！ 先看po姐的图片，有个直观理解  我们先进行差分： $$\sum_{i=0}^{n} \sum_{d=0}^{\lfloor\frac{an+b}{c}\rfloor-1}[\lfloor\frac{ai+b}{c}\rfloor\ge d+1]$$ 应用最开始说的式子， $$\sum_{i=0}^{n} \sum_{d=0}^{\lfloor\frac{an+b}{c}\rfloor-1}[ai+b\ge cd+c]$$ $$\sum_{i=0}^{n} \sum_{d=0}^{\lfloor\frac{an+b}{c}\rfloor-1}[ai+b> cd+c-1]$$ $$\sum_{i=0}^{n} \sum_{d=0}^{\lfloor\frac{an+b}{c}\rfloor-1}[i>\lfloor\frac{cd+c-b-1}{a}\rfloor]$$ 发现这个谓词其实就是$n-\lfloor\frac{cd+c-b-1}{a}\rfloor$ $$\sum_{d=0}^{\lfloor\frac{an+b}{c}\rfloor-1}n-\lfloor\frac{cd+c-b-1}{a}\rfloor$$ 转化为递归的形式！ $$f(a,b,c,n)=n\lfloor\frac{an+b}{c}\rfloor -f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)$$ *注意特判a=0的情况！* ```cpp int f(int a,int b,int c,int n) { if(a==0) return mul(n+1,b/c); if(a>=c||b>=c) return add(f(a%c,b%c,c,n),mul((LL)n*(n+1)/2%md,a/c),mul(n+1,b/c)); int m=((LL)a*n+b)/c; return sub(mul(n,m),f(c,c-b-1,a,m-1)); } ``` ----------- ### 例题：EOJ799 ~~日，模数写错调了1h~~ 这道题的关键是求出 $$\sum_{i=0}^{n} \left[\left\lfloor \frac{ai+b}{c} \right\rfloor \bmod d \le t\right]$$ **性质：** $$[a \bmod b \le c]= \left\lfloor \frac{a}{b} \right\rfloor - \left \lfloor \frac{a-c-1}{b} \right \rfloor$$ 于是： $$ans=\sum_{i=0}^{n} \left[\left\lfloor \frac{ai+b}{c} \right\rfloor \bmod d \le t\right]$$ $$=\sum_{i=0}^{n} \left\lfloor \frac{ai+b}{cd} \right\rfloor-\left\lfloor \frac{\left\lfloor \frac{ai+b}{c} \right\rfloor - (t + 1)}{d} \right\rfloor $$ $$=f(a,b,cd,n)-f(a,b-c(t+1),cd,n)$$ 还有一些小问题： $f(a,b,c,d)$中的b可能是负数，此时它可以化为： $$f(a,b,c,n)=f(a,b+\lambda c,c,n)-\lambda(n+1),\lambda=\left\lceil \frac{-b}{c} \right\rceil$$ ----------- 还有2种类欧没学，等用到了再说吧。 我学了一个假类欧。真类欧请见[LOJ#138. 类欧几里得算法](https://www.cnblogs.com/zzqsblog/p/8904010.html)。~~（您可学着去~~