FLOOR SUM (简单类欧板子)学习笔记

· · 个人记录

要求实现如下一个函数的快速运算:

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

先去除掉 a\ge c,b\ge c 情况下的贡献:

\lfloor\frac{ai+b}{c}\rfloor = \lfloor \frac{(a\mod c)\cdot i+\lfloor\frac{a}{c}\rfloor\cdot ci+(b\mod c)+\lfloor\frac{b}{c}\rfloor\cdot c}{c}\rfloor \sum_{i=0}^{n} \lfloor\frac{ai+b}{c}\rfloor=\lfloor\frac{a}{c}\rfloor \cdot \frac{n(n+1)}{2}+\lfloor\frac{b}{c}\rfloor\cdot(n+1)+\lfloor \frac{(a\mod c)\cdot i+(b\mod c)}{c}\rfloor

所以可以先这样操作:

if (a>=c){ans+=a/c*n*(n+1)/2; a%=c;}
if (b>=c){ans+=b/c*(n+1); b%=c;}

现在多了 a<c,b<c 的条件，现在不妨把式子稍微搞长一点:

\sum_{i=0}^{n} \lfloor\frac{ai+b}{c}\rfloor=\sum_{i=0}^{n} \sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}1=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^{n}[j+1\le\lfloor\frac{ai+b}{c}\rfloor] [j+1\le\lfloor\frac{ai+b}{c}\rfloor]=[cj+c\le ai+b]=[i>\lfloor\frac{cj+c-b-1}{a}\rfloor] \sum_{i=0}^{n} \lfloor\frac{ai+b}{c}\rfloor=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^{n}[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)

此时设 m=\lfloor\frac{an+b}{c}\rfloor，则有

floor\_sum(a,b,c,n)=mn-floor\_sum(c,c-b-1,a,m-1)

那么就可以以 O(\log N) 的复杂度递归解决了owo

code

inline long long floor_sum(long long a,long long b,long long c,long long n){
long long ans=0;
if (a>=c){ans+=a/c*n*(n+1)/2; a%=c;}
if (b>=c){ans+=b/c*(n+1); b%=c;}
long long m=(a*n+b)/c;
if (m==0) return ans;
ans+=m*n-floor_sum(c,c-b-1,a,m-1);
return ans;
}