做胡策的时候遇到了这样的问题：
求：
\[\max_{i=0}^n \{(ai+b) \bmod c\} \]一个简单的方法是：二分答案 \(mid\)，然后转化为计算：
\[\sum_{i=0}^n [(ai+b)\bmod c\ge mid]=\sum_{i=0}^n \lfloor\dfrac{ai+b+(c-mid)}{c}\rfloor-\lfloor\dfrac{ai+b}{c}\rfloor \]分别使用类欧计算，复杂度 \(O(\log^2 c)\)。
事实上可以做到 1log：
令 \(F(a,b,c,n)=\max\limits_{i=0}^n \{(ai+b) \bmod c\},G(a,b,c,n)=\min\limits_{i=0}^n \{(ai+b) \bmod c\}\)，尝试类欧：
边界：\(F(a,b,c,0)=F(0,b,c,n)=G(a,b,c,0)=G(0,b,c,n)=b\bmod c\)。
考虑两种转移：当 \(a\) 较大时，有 \(F(a,b,c,n)=F(a\bmod c,b\bmod c,c,n)\)，\(G\) 亦然。
当 \(c\) 较大时，我们尝试交换 \(a,c\) 的地位。
若 \(\dfrac{ai+b}{c}=j\cdots k\)，则最大的 \(i\) 满足 \(i=\lfloor\dfrac{c(j+1)-b-1}{a}\rfloor\)
\[F(a,b,c,n)=\max_{i=0}^n \{(ai+b) \bmod c\}\\ =\max_{j=0}^{\lfloor\frac{an+b}{c}\rfloor} (a\lfloor\dfrac{c(j+1)-b-1}{a}\rfloor+b-cj)\\ =c-1-\min_{j=0}^{\lfloor\frac{an+b}{c}\rfloor}(c-1-a\lfloor\dfrac{cj+c-b-1}{a}\rfloor-b+cj)\\ =c-1-G(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor) \]注意到当 \(j\) 为 \(\lfloor\frac{an+b}{c}\rfloor\) 时对应的 \(i\) 不一定在 \([1,n]\) 内。因此正确的转移式是：
\[F(a,b,c,n)=\max((an+b) \bmod c,c-1-G(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)) \]同样有 \(G(a,b,c,n)=\min(b,a-1-F(c,c-b-1,a,\lfloor\dfrac{an+b}{c}\rfloor-1))\)。
标签：lfloor,frac,ai,dfrac,bmod,rfloor,问题,类欧,经典 From： https://www.cnblogs.com/havzriu/p/16947180.html