类欧几里得算法

本文最后编辑于2018年9月14日。


推导

有时候需要快速计算如下式子(比如数据范围都是1e9)

\(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)}{a*d-b*c}\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