类欧几里得算法总结

定义

$$f(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor$$

$$g(a,b,c,n)=\sum_{i=0}^ni\lfloor {ai+b \over c} \rfloor$$

$$h(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor^2$$

f

$$f(a,b,c,n)={a\over c}\times n \times {n+1 \over 2} +{b \over c} \times (n+1)+f(a \%c,b\%c,c,n)$$

$$f(a,b,c,n)=\sum_{i=0}^n\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[ai \geq cj+c-b]$$

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

$$=\sum_{j=0}^{m}(n-{cj+c-b-1 \over a})$$

$$=m\times n-\sum_{j=0}^{m}{cj+c-b-1 \over a}$$

$$f(a,b,c,n)=m\times n-f(c,c-b-1,a,m-1)$$

$$f(a,b,c,n)={an+b \over c}\times n-f(c,c-b-1,a,{an+b \over c}-1)$$

g

$$g(a,b,c,n)={a\over c}\times n \times (n+1)\times {2n+1 \over 6}+{b\over c}\times n\times {n+1\over 2}+g(a\%c,b\%c,c,n)$$

$a$和$b$都小于$c$和上面一样推

$$g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

$$={1\over2}\sum_{j=0}^{m-1}(n+1+{cj+c-b-1 \over a})\times(n-{cj+c-b-1 \over a})$$

$$={1\over2}\sum_{j=0}^{m-1}n\times (n+1)-{cj+c-b-1 \over a}+({cj+c-b-1 \over a})^2$$

$$g(a,b,c,n)={1 \over 2}[(n+1)\times n\times m-f(c,c-b-1,a,m-1)-g(c,c-b-1,a,m-1) ]$$

h

$$h(a,b,c,n)=({a\over c})^2\times {n(n+1)(2n+1)\over 6}+({b\over c})^2\times(n+1)+{a\over c}\times{b\over c}\times n(n+1)+h(a\%c,b\%c,c,n)+2\times {a\over c}\times g(a\%c,b\%c,c,n)+2\times {b\over c}\times f(a\%c,b\%c,c,n)$$

$$n^2=2\times \frac{n(n+1)}{2}-n=2\sum_{i=0}^ni-n$$

$$h(a,b,c,n)=\sum_{i=0}^n(2\times \sum_{j=1}^{(ai+b)/c}j-{ai+b\over c})$$

$$=2\times \sum_{j=0}^{m-1}(j+1)\times\sum_{i=0}^n[{ai+b \over c} \geq j+1]-f(a,b,c,n)$$

$$h(a,b,c,n)=2\times \sum_{j=0}^{m-1}(j+1)*(n-{cj+c-b-1 \over a})-f(a,b,c,n)$$

$$h(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)$$

例题 bzoj 3817

题意

$$\large \sum_{d=1}^{n} (-1)^{\lfloor \sqrt{d\times r\times d} \rfloor}$$

题解

\begin{align} -1^{dx } & =1-2( dx \% 2) \\ &=1-2(dx – \frac{dx}{2} * 2) \\ &= 1+4\frac{dx}{2} + 2 dx \end{align}

$$原式 =n + 4 \sum_{d=1}^{n} \frac{dx}{2}-2\sum_{d=1}^{n}dx$$

×