题目
求 \(f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor\)
题解
当 \(a\ge c\) 或 \(b\ge c\) 时，
\(\begin{aligned}
\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor & = \sum\limits_{i=0}^n\lfloor\frac ac\rfloor i+\lfloor\frac bc\rfloor+\lfloor\tfrac{(a\bmod c)i+b\bmod c}c\rfloor
\\ & =\lfloor\frac ac\rfloor(\frac 12n(n+1))+(n+1)\lfloor\frac cb\rfloor+f(a\bmod c,b\bmod c,c,n)
\end{aligned}\)
那么此时就满足 \(a<c,b<c\) 了。然后
\(\begin{aligned}
\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor&=\sum\limits_{i=0}^n\sum\limits_{j=0}^{\lfloor\frac{ai+b}c\rfloor-1}1
\end{aligned}\)
为了方便，设 \(m=\lfloor\frac{an+b}c\rfloor\)
\(
\begin{aligned}
原式=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n[j<\lfloor\frac{ai+b}c\rfloor]
\end{aligned}\)
给这个式子略微变一下形
\[j<\lfloor\frac{ai+b}c\rfloor \]\[j+1\le \frac{ai+b}c \]\[i>\frac{cj+c-b-1}a \]\(\begin{aligned} \sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n[j<\lfloor\frac{ai+b}c\rfloor] &= \sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n[i>\lfloor\frac{cj+c-b-1}a\rfloor]\\&=\sum\limits_{i=0}^{m-1}n-\lfloor\frac{cj+c-b-1}a\rfloor\\&=nm-f(c,c-b-1,a,m-1) \end{aligned}\)
复杂度的话，因为这样每次将 \(a,c\) 交换，然后取模，这样的形式和欧几里得算法极其相似，复杂度是 \(O(\log a)\) 的。同时递归边界是 \(a=0\)，答案就不用讲了吧。
题目
来看一下进阶版
\(g(a,b,c,n)=\sum\limits_{i=0}^ni\lfloor\frac{ai+b}c\rfloor\)
\(h（a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2\)
题解
未完待续
标签：lfloor,frac,limits,ai,欧几里得,笔记,算法,rfloor,sum From： https://www.cnblogs.com/mekoszc/p/17016987.html