类欧几里得算法

推导

有时候需要快速计算如下式子(比如数据范围都是 $10^9$ )

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

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

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

先推导一下$f(a,b,c,n)$，分两种情况

1.当$a\ge c$或$b \ge c$时，

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

2.当$a<c$且$b<c$时，令$m=\lfloor\frac{an+b}{c}\rfloor$

$f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=1}^{m}\left[\lfloor\frac{ai+b}{c}\rfloor\ge j\right]$

$f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=0}^{m-1}\left[\lfloor\frac{ai+b}{c}\rfloor\ge j+1\right]$

$f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=0}^{m-1}\left[ai\ge jc+c-b\right]$

$f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=0}^{m-1}\left[ai> jc+c-b-1\right]$

$f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=0}^{m-1}\left[i>\frac{jc+c-b-1}{a}\right]$

最后交换求和

$f(a,b,c,n)=\sum_{j=0}^{m-1}(n-\lfloor\frac{jc+c-b-1}{a}\rfloor)$

得到

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

因为系数$a,c$变成了$c,a\%c$，所以叫类欧几里得算法。

题目

1. bzoj2987: Earthquake

给定a,b,c,求满足方程Ax+By<=C的非负整数解

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

负数再变形一下，可以看成把x从大到小遍历

$ans=\sum_{x=0}^{\lfloor\frac{c}{a}\rfloor}\lfloor\frac{c\%a+ax}{b}\rfloor+1$

2. 牛客网暑期ACM多校训练营（第十场）Rikka with Ants

在二维坐标系有两条直线$y=\frac{a}{b}x,y=\frac{c}{d}x$。对于每一条直线，有一只蚂蚁从(1,0)出发，只能向上或向右走一格，并且蚂蚁一直都在直线下方，每次优先向上走，如果越过了直线就改为向右走。问对于这两个蚂蚁走过的点的交集大小。

斜率相等时交集点数无穷大。

对于直线$y=\frac{a}{b}x$，走到的点为$\frac{a}{b}(x-1)-1 < y \le \frac{a}{b}x,x\ge 1$

假设直线$y=\frac{c}{d}x$斜率较小，那么交集为

$\frac{a}{b}(x-1)-1 < y \le \frac{c}{d}x, 1 \le x \le n$

其中

$n=\lfloor\frac{d(a+b)}{ad-bc}\rfloor$

最终要求的式子

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

参考资料：

https://blog.csdn.net/WorldWide_D/article/details/54730588