\(\rm L\): 我们现在要解 \(ax \equiv 1\pmod p\) 的同余方程
\(\rm P\): 用欧拉定理来求逆元是熟知的
\(\rm L\): 现在进行另一种处理，\(x\) 是 \(ax+py-1=0\) 这个不定方程的整数解
\(\rm P\): 根据裴蜀定理，可以推广为求 \(ax+by=(a,b)\) 的整数解
\(\rm L\): 考虑将其变形为 \(ax+(b+ak-ak)y=(a,b)\)
\(\rm P\): 整理一下就是 \((ak+b)y+a(x-ky)=(a,b)\)
\(\rm L\): 你知道辗转相除法的过程吗
\(\rm P\): 嗯，利用 \((a,b) = (b,a\bmod b)\) 递归求解
\(\rm L\): 上面的式子是类似的
\(\rm P\): 是的，要求关于 \(a,b\) 的解，只要求 \(b,a\bmod b\) 的解
\(\rm L\): 所以这个过程被称做扩展欧几里得，试着分析其复杂度
\(\rm P\): 就是辗转相除法的复杂度，但是不会证明
\(\rm L\): 考虑 \(Fib(n) \bmod Fib(n-1) = Fib(n-2)\)
\(\rm P\): 嗯，\(a \bmod b \leq a-b\)，而 \(Fib(n) \bmod Fib(n-1) = Fib(n)-Fib(n-1)\)，\(T(Fib(n)) = O(n)\)，所以 \(T(n) = O(\log n)\)
\(\rm L\): 很好的复杂度和常数，要当年补模拟赛那道模 \(998244353\) 用 exgcd 而不是费马小定理就不会 95pts 了/kk
\(\rm P\): 哪道啊
\(\rm L\): 那题现在交不了了/kk，尝试着用刚刚的方法求 \(\sum^n_{i=0}\lfloor\frac{ai+b}{c}\rfloor\)
\(\rm P\): 我推导一下:
\(\begin{align}\sum^n_{i=0}\lfloor\frac{ai+b}{c}\rfloor &= \sum^n_{i=0}\sum^{\lfloor\frac{ai+b}{c}\rfloor-1}_{j=0}1 \nonumber\\ &=\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^n_{i=0}1[j<\lfloor\frac{ai+b}{c}\rfloor] \nonumber\\ &=\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^n_{i=0}1[i>\lfloor\frac{cj+c-b-1}{a}\rfloor] \nonumber\\ &= n\lfloor\frac{an+b}{c}\rfloor-\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{i=0} (\lfloor\frac{c\bmod i+c-b-1}{a}\rfloor+\lfloor\frac{c}{a}\rfloor i) \nonumber\\ &= (n-\frac{\lfloor\frac{an+b}{c}\rfloor-1}{2}\lfloor\frac{c}{a}\rfloor)\lfloor\frac{an+b}{c}\rfloor-\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{i=0} (\lfloor\frac{c\bmod i+c-b-1}{a}\rfloor)\nonumber\end{align}\)
\(\rm L\): 很好，用 \(f(n,a,b,c)\) 表示 \(\sum^n_{i=0}\lfloor\frac{ai+b}{c}\rfloor\)，可以得到 \(\begin{align}f(n,a,b,c) = (n-\frac{\lfloor\frac{an+b}{c}\rfloor-1}{2}\lfloor\frac{c}{a}\rfloor)\lfloor\frac{an+b}{c}\rfloor-f(\lfloor\frac{an+b}{c}\rfloor-1,c\bmod a,c-b-1,a)\nonumber\end{align}\)
，接下来试着求 \(\begin{align}g(n,a,b,c) &= \sum^n_{i=0}(\lfloor\frac{ai+b}{c}\rfloor)^2 \nonumber\\ h(n,a,b,c) &= \sum^n_{i=0}i\lfloor\frac{ai+b}{c}\rfloor\nonumber\end{align}\)
\(\rm P\): 看上去长得差不多啊，
\(\begin{align} g(n,a,b,c) &= \sum^n_{i=0}(\lfloor\frac{ai+b}{c}\rfloor)^2 \nonumber \\ &= \sum^n_{i=0}\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{k=0}1 \nonumber \\ &= \sum^n_{i=0}\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{k=0} 1[j,k < \lfloor\frac{ai+b}{c}\rfloor] \nonumber \\ &= 2\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^j_{k=0}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)-\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)\nonumber \\ &= n\lfloor\frac{an+b}{c}\rfloor^2 -f(\lfloor\frac{an+b}{c}\rfloor-1,c,c-b-1,a)-2h(\lfloor\frac{an+b}{c}\rfloor,c,c-b-1,a)\nonumber\end{align}\)
\(\begin{align}h(n,a,b,c) &= \sum^n_{i=0}i\lfloor\frac{ai+b}{c}\rfloor \nonumber \\ &=\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}\sum^n_{i=0}i[i>\lfloor\frac{cj+c-b-1}{a}\rfloor] \nonumber \\ &=\sum^{\lfloor\frac{an+b}{c}\rfloor-1}_{j=0}(\frac{n(n+1)}{2}-\frac{\lfloor\frac{cj+c-b-1}{a}\rfloor(\lfloor\frac{cj+c-b-1}{a}\rfloor-1)}{2}) \nonumber \\ &= \frac{1}{2}(n(n+1))\lfloor\frac{an+b}{c}\rfloor-g(\lfloor\frac{an+b}{c}\rfloor-1,c,c-b-1,a)-f(\lfloor\frac{an+b}{c}\rfloor-1,c,c-b-1,a)\nonumber \end{align}\)
就是 \(g\) 和 \(h\) 互相推，不过好难写啊/yun
【模板】二元一次不定方程 (exgcd)
【模板】类欧几里得算法