1.用途
在\(O(logn)\)的时间复杂度内求出\(\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor\)
2.推导
1.当a>c且b>c时
\(\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor\)
\(=\sum_{i=0}^{n}\lfloor\frac{(\lfloor\frac{a}{c}\rfloor*c+a\%c)i+ \lfloor\frac{b}{c}\rfloor*c+b\%c}{c}\rfloor\)
\(=\sum_{i=0}^{n}\lfloor \lfloor\frac{a}{c}\rfloor*i+ \lfloor\frac{b}{c}\rfloor+\frac{a\%c*i+b\%c}{c}\rfloor\)
\(=\sum_{i=0}^{n} \lfloor\frac{a}{c}\rfloor*i+ \lfloor\frac{b}{c}\rfloor+\lfloor\frac{a\%c*i+b\%c}{c}\rfloor\)
\(= \lfloor\frac{a}{c}\rfloor*\frac{n*(n+1)}{2}+ \lfloor\frac{b}{c}\rfloor*(n+1)+\sum_{i=0}^{n}\lfloor\frac{a\%c*i+b\%c}{c}\rfloor\)
2.当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<= \lfloor\frac{ai+b}{c}\rfloor-1]\)
\(= \sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^{n}[j< \frac{ai+b}{c}]\)
\(= \sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^{n}[\lfloor\frac{j*c-b}{a}\rfloor< i]\)
$= \sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}n-\lfloor\frac{j*c-b}{a}\rfloor $
$= n* \lfloor\frac{an+b}{c}\rfloor-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\lfloor\frac{c*j-b}{a}\rfloor $
标签：lfloor,frac,ai,欧几里德,rfloor,sum From： https://www.cnblogs.com/Owen1234/p/18416955