类欧几里得
简介
基础的类欧几里得有三种形式，可以用来快速求出者三种形式的值。
\[f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor\]
\[g(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor\]
\[h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2\]
令 \(m=\lfloor\frac{ai+b}c\rfloor\)
推\(f\)式(最简单)
\[f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor\]
如果 \(a\ge c\) 或 \(b\ge c\):
\[\begin{aligned}
f(a,b,c,n)&=\lfloor\frac ac\rfloor\frac {n(n+1)}2+\lfloor\frac bc\rfloor(n+1)+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor \\
&=\lfloor\frac ac\rfloor\frac {n(n+1)}2+\lfloor\frac bc\rfloor(n+1)+f(a\bmod c,b\bmod c,c,n)
\end{aligned}\]
如果 \(a,b\lt c\):
\[\begin{aligned}
f(a,b,c,n)&=\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}^{m-1}\sum_{i=0}^n[j\lt\lfloor\frac {ai+b}c\rfloor] \\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[cj\lt(ai+b)-c+1] \\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i] \\
&=\sum_{j=0}^{m-1}(n-\lfloor\frac{cj+c-b-1}a\rfloor) \\
&=nm-\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor \\
&=nm-f(c,c-b-1,a,m-1)
\end{aligned}\]
递归即可。
推\(g\)式
\[g(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor\]
如果 \(a\ge c\) 或 \(b\ge c\):
\[\begin{aligned}
g(a,b,c,n)&=\lfloor\frac ac\rfloor\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor\frac{n(n+1)}2+\sum_{i=0}^ni\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor \\
&=\lfloor\frac ac\rfloor\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor\frac{n(n+1)}2+g(a\bmod c,b\bmod c,c,n)
\end{aligned}\]
如果 \(a,b\lt c\):
\[\begin{aligned}
g(a,b,c,n)&=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor \\
&=\sum_{i=0}^ni\sum_{j=0}^{\lfloor\frac{ai+b}c\rfloor-1}1 \\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[j\lt\lfloor\frac{ai+b}c\rfloor]i \\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[cj\lt(ai+b)-c+1]i \\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i]i \\
&=\sum_{j=0}^{m-1}\frac{(n-\lfloor\frac{cj+c-b-1}a\rfloor)(n+\lfloor\frac{cj+c-b-1}a\rfloor+1)}2 \\
&=\frac12\sum_{j=0}^{m-1}(n(n+1)-\lfloor\frac{cj+c-b-1}a\rfloor-\lfloor\frac{cj+c-b-1}a\rfloor^2) \\
&=\frac m2n(n+1)-\frac12\sum_{j=0}^{m-1}(\lfloor\frac{cj+c-b-1}a\rfloor+\lfloor\frac{cj+c-b-1}a\rfloor^2) \\
&=\frac m2n(n+1)-\frac12(f(c,c+b-1,a,m-1)+h(c,c+b-1,a,m-1))
\end{aligned}\]
递归时需要用到 \(f\) 和 \(h\)。
推\(h\)式
\[h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2\]
如果 \(a\ge c\) 或 \(b\ge c\):
\[\begin{aligned}
h(a,b,c,n)=&\sum_{i=0}^n(\lfloor\frac ac\rfloor i+\lfloor\frac bc\rfloor)^2+\sum_{i=0}^n2(\lfloor\frac ac\rfloor i+\lfloor\frac bc\rfloor)\lfloor\frac{(a\bmod c)i+(b\bmod c)}c\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2 \\
=&\lfloor\frac ac\rfloor^2\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor^2(n+1)+2\lfloor\frac ac\rfloor\lfloor\frac bc\rfloor\frac{n(n+1)}2 \\
&+2\sum_{i=0}^n\lfloor\frac ac\rfloor i\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+2\sum_{i=0}^n\lfloor\frac bc\rfloor\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2 \\
=&\lfloor\frac ac\rfloor^2\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor^2(n+1)+\lfloor\frac ac\rfloor\lfloor\frac bc\rfloor n(n+1) \\
&+2\lfloor\frac ac\rfloor g(a\bmod c,b\bmod c,c,n)+2\lfloor\frac bc\rfloor f(a\bmod c,b\bmod c,c,n)+h(a\bmod c,b\bmod c,c,n)
\end{aligned}\]
如果 \(a,b\lt c\):
\[\begin{aligned}
h(a,b,c,n)&=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2 \\
&=\sum_{i=0}^n(2\sum_{j=1}^{\lfloor\frac{ai+b}c\rfloor}j-\lfloor\frac{ai+b}c\rfloor) 将平方展开成求和式 \\
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[j\lt\lfloor\frac{ai+b}c\rfloor]-f(a,b,c,n) \\
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[cj\lt(ai+b)-c+1]-f(a,b,c,n) \\
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i]-f(a,b,c,n) \\
&=2\sum_{j=0}^{m-1}(j+1)(n-\lfloor\frac{cj+c-b-1}a\rfloor)-f(a,b,c,n) \\
&=2\sum_{j=0}^{m-1}(j+1)n-2\sum_{j=0}^{m-1}(j+1)\lfloor\frac{cj+c-b-1}a\rfloor-f(a,b,c,n) \\
&=2n\frac{m(m+1)}2-2\sum_{j=0}^{m-1}j\lfloor\frac{cj+c-b-1}a\rfloor-2\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor-f(a,b,c,n) \\
&=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)
\end{aligned}\]
