类欧几里得

类欧几里得

​ 给定三个式子.对其进行化简.

  • \(f(a,b,c,n)=\sum_{i=0}^n⌊\frac{ai+b}{c}⌋\)
  • \(g(a,b,c,n)=\sum_{i=0}^ni⌊\frac{ai+b}{c}⌋\)
  • \(h(a,b,c,n)=\sum_{i=0}^n⌊\frac{ai+b}{c}⌋^2\)

设\(m=\lfloor\frac{an+b}{c}\rfloor\)

给出一个公式详表

\(\begin{aligned}& \sum_{i=0}^n=(n+1)\\&\sum_{i=0}^ni=\frac{n(n+1)}{2}\\&\sum_{i=1}^ni^2=\frac{n(n+1)(2n+6)}{2}\\&(a+b)^2=a^2+b^2+2ab\\&n^2=2*\frac{n(n+1)}{2}-n=2\sum_{i=0}^ni-n\end{aligned}\)

化简①

分析当\(a,b\)>=\(c\)时

\(\begin{aligned}f& =\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor \\ & = \sum_{i=0}^ni\lfloor\frac{a}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\frac{a\ mod\ c+b~mod~c}{c}\\&=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a~mod~c,b~mod~c,c,n)\end{aligned}\)

分析当\(a,b\)<\(c\)时

\(\begin{aligned}f&=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\\&=\sum_{i=0}^n\sum_{j=1}^m[\lfloor\frac{ai+b}{c}\rfloor\geq j]&①\\&=\sum_{i=0}^n\sum_{j=0}^{m-1}[\lfloor\frac{ai+b}{c}\rfloor\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>\lfloor \frac{cj+c-b-1}{a}\rfloor]\end{aligned}\)

①把对一个式子求和直接转换成多个满足条件时的多个1相加.

可以发现对于每一个\(i>\lfloor \frac{cj+c-b-1}{a}\rfloor \)时才会产生1的贡献.

\(\begin{aligned}f&=\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}\)

剩余直接暴力即可.

化简②

考虑\(a,b\)>=\(c\)的情况

\(\begin{aligned}g&=\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor\\&=\sum_{i=0}^ni^2\lfloor\frac{a}{c}\rfloor+\sum_{i=0}^ni\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\frac{(a~mod~c)i+b~mod~c}{c}\\&=\frac{n(n+1)(2n+6)}{2}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor+g(a\%c,b\%c,c,n)\end{aligned}\)

之后考虑\(a,b\)<\(c\)的情况.

与化简①类似.

\(\begin{aligned}g&=\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor\\&=\sum_{i=0}^ni\sum_{j=1}^m[\lfloor\frac{ai+b}{c}\rfloor\geq j]\\&=\sum_{i=0}^ni\sum_{j=1}^m[ai\geq cj-b]\\&=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]\end{aligned}\)

可以发现,每一个\(j\)只有当满足条件的时候才会连续\(i\)次产生1的贡献(共\(i\)的贡献).

并且对于每一个需要统计的答案之间公差是相同的,所以可以用等差数列求和公式化简.

\(\begin{aligned}g&=\sum_{j=0}^{m-1}\frac{(\lfloor\frac{cj+c-b-1}{a}\rfloor+1+n)(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)}{2}\\&=\frac{1}{2}\sum_{j=0}^{m-1}(\lfloor\frac{cj+c-b-1}{a}\rfloor+1+n)(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)\\&=\frac{1}{2}\Big[\sum_{j=0}^{m-1}(\lfloor\frac{cj+c-b-1}{a}\rfloor*n-\lfloor\frac{cj+c-b-1}{a}\rfloor^2+n-\lfloor\frac{cj+c-b-1}{a}\rfloor\\&~~~~~+n^2-n*\lfloor\frac{cj+c-b-1}{a}\rfloor)\Big]\\&=\frac{1}{2}\Big[\sum_{j=0}^{m-1}(n^2+n-\lfloor\frac{cj+c-b-1}{a}\rfloor^2-\lfloor\frac{cj+c-b-1}{a}\rfloor)\Big]\\&=\frac{1}{2}\sum_{j=0}^{m-1}\Big[\big[n*(n+1)\big]-\lfloor\frac{cj+c-b-1}{a}\rfloor^2-\lfloor\frac{cj+c-b-1}{a}\rfloor\Big ]\\&=\frac{1}{2}\Big[\sum_{j=0}^{m-1}\big[n*(n+1)\big]-\sum_{j=0}^{m-1}\big[\lfloor\frac{cj+c-b-1}{a}\rfloor\big]-\sum_{j=0}^{m-1}\big[\lfloor\frac{cj+c-b-1}{a}\rfloor^2\big]\Big] \\&=\frac{1}{2}\Big[nm(n+1)-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1)\Big]\end{aligned}\)

化简③

分析当\(a,b>=c\)的情况.

\(\begin{aligned}h&=\sum_{i=0}^{n}\lfloor\frac{\big(\lfloor\frac{a}{c}\rfloor*c+(a~mod~c)\big)i+\lfloor\frac{b}{c}\rfloor*c+(b~mod~c)}{c}\rfloor^2\\&=\sum_{i=0}^n\big(\lfloor\frac{\big(\lfloor\frac{a}{c}\rfloor*c+(a\ mod\ c)\big)i}{c}\rfloor+\lfloor\frac{c*\lfloor\frac{b}{c}\rfloor+(b~mod~c)}{c}\rfloor\big)^2\\&=\sum_{i=0}^n\big(\lfloor\frac{(b~mod~c)+(a\ mod\ c)i}{c}\rfloor+\lfloor\frac{c*\lfloor\frac{b}{c}\rfloor+\lfloor\frac{a}{c}\rfloor*c}{c}\rfloor\big)^2\\&=\sum_{i=0}^{n}\big(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor\big)^2+\sum_{i=0}^n\big(\lfloor\frac{(b~mod~c)+(a~mod~c)i}{c}\rfloor\big)^2+2\sum_{i=0}^n\big(\lfloor\frac{(b~mod~c)+(a~mod~c)i}{c}\rfloor*(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)\big)\\&=\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i)^2+\sum_{i=0}^n(\lfloor\frac{b}{c}\rfloor)^2+\sum_{i=0}^n\big(2\lfloor\frac{a}{c}\rfloor i\lfloor\frac{b}{c}\rfloor\big)+\sum_{i=0}^n\big(\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor\big)^2\\&~~~~+2\lfloor\frac{a}{c}\rfloor\sum_{i=0}^ni\big(\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor\big)+2\lfloor\frac{b}{c}\rfloor\sum_{i=0}^n\big(\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor\big)\\&=\frac{n(n+1)(2n+6)}{2}\lfloor\frac{a}{c}\rfloor^2+(n+1)\lfloor\frac{b}{c}\rfloor^2+2*\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+2\lfloor\frac{a}{c}\rfloor g(a~mod~c,b~mod~c,c,n)\\&~~~~~+2\lfloor\frac{b}{c}\rfloor f(a~mod~c,b~mod~c,c,n)+h(a~mod~c,b~mod~c,c,n)\end{aligned}\)

从而转化成了\(a,b\)<\(c\)的情况.

根据上面公式表里对\(n^2\)的化简可知.

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

可以直接把\(n\)当做\(\lfloor\frac{ai+b}{c}\rfloor\)带入.

\(\begin{aligned}h&=\sum_{i=0}^n\big(2\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor}j-\lfloor\frac{ai+b}{c}\rfloor\big)\\&=\sum_{i=0}^n(2\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor}j)-f(a,b,c,n)\\&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[\lfloor\frac{ai+b}{c}\rfloor\geq j+1]-f(a,b,c,n)\\&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^{n}\big[i>\lfloor\frac{cj+c-b-1}{a}\rfloor\big]-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)\\&=m*2*\frac{n(n+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(n+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)\end{aligned}\)


以上.

类欧几里得》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注