本文最后更新于:2020年8月24日 下午

推导

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

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

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

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

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

1.当aca\ge cbcb \ge c时,

f(a,b,c,n)=f(a%c,b%c,c,n)+n(n+1)2ac+(n+1)bcf(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<ca<cb<cb<c时,令m=an+bcm=\lfloor\frac{an+b}{c}\rfloor

f(a,b,c,n)=i=0nj=1m[ai+bcj]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)=i=0nj=0m1[ai+bcj+1]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)=i=0nj=0m1[aijc+cb]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)=i=0nj=0m1[ai>jc+cb1]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)=i=0nj=0m1[i>jc+cb1a]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)=j=0m1(njc+cb1a)f(a,b,c,n)=\sum_{j=0}^{m-1}(n-\lfloor\frac{jc+c-b-1}{a}\rfloor)

得到

f(a,b,c,n)=nmf(c,cb1,a,m1)f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)

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

题目

1. bzoj2987: Earthquake

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

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

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

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

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

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

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

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

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

ab(x1)1<ycdx,1xn\frac{a}{b}(x-1)-1 < y \le \frac{c}{d}x, 1 \le x \le n

其中

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

最终要求的式子

x=0n1cx+cdx=0n1axb1\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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

偏序集 上一篇
后缀自动机学习笔记 下一篇