要求这么一类问题
\[ \begin{aligned} f(a,b,c,n) &=\sum_{i=0}^n \left\lfloor{ai+b\over c}\right\rfloor \end{aligned} \]
开始颓柿子
\[ \begin{aligned} f(a,b,c,n) &=(n+1)\left\lfloor{b\over c}\right\rfloor\\end{aligned} \]
\[ \begin{aligned} f(a,b,c,n) &=\sum_{i=0}^n \left\lfloor{ai+b\over c}\right\rfloor\&=\sum_{i=0}^n \left\lfloor{(a\bmod c)i+(b\bmod c)\over c}\right\rfloor+{n(n+1)\over 2}\left\lfloor{a\over c}\right\rfloor+(n+1)\left\lfloor{b\over c}\right\rfloor\&=f(a\bmod c,b\bmod c,n)+{n(n+1)\over 2}\left\lfloor{a\over c}\right\rfloor+(n+1)\left\lfloor{b\over c}\right\rfloor\\end{aligned} \]
令\(m=\left\lfloor{an+b\over c}\right\rfloor\)，显然有\(m\leq n\)
\[ \begin{aligned} f(a,b,c,n) &=\sum_{i=0}^n \left\lfloor{ai+b\over c}\right\rfloor\&=\sum_{i=0}^n \sum_{j=1}^m\left[\left\lfloor{ai+b\over c}\right\rfloor\geq j\right]\&=\sum_{i=0}^n \sum_{j=0}^{m-1}\left[\left\lfloor{ai+b\over c}\right\rfloor\geq j+1\right]\&=\sum_{i=0}^n \sum_{j=0}^{m-1}\left[ai>cj+c-b-1\right]\&=\sum_{i=0}^n \sum_{j=0}^{m-1}\left[i>\left\lfloor{cj+c-b-1\over a}\right\rfloor\right]\&=\sum_{j=0}^{m-1}n-\left\lfloor{cj+c-b-1\over a}\right\rfloor\&=nm-f(c,c-b-1,a,m-1)\\end{aligned} \]
发现这个过程中\(a,c\)的迭代类似\(gcd\)，所以这个算法的复杂度也是\(O(\log n)\)的
另外的两个扩展不学了……
原文：https://www.cnblogs.com/yuanquming/p/11777184.html