类欧几里得算法

定义

给定\(a,b,c,n\)求对应函数的值:

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

\(g(a,b,c,n)=\sum_{i=0}^n i\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{an+b}{c}\rfloor\)

  1. \(f(a,b,c,n)\)

    首先考虑\(a,b\geq c\)的情况:

    根据带余除法的定义,\(a=\lfloor\frac{a}{c}\rfloor\cdot c+(a\bmod c)\)\(b\)同理。

    \[\begin{aligned}原式 & =\sum_{i=0}^n\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\bmod c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\bmod c)}{c}\rfloor\\ & =\sum_{i=0}^n\lfloor\frac{a}{c}\rfloor i+\sum_{i=0}^n\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor\\ & =\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor\\ & =\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a\bmod c,b\bmod c,c,n)\end{aligned} \]

    这样就转化成了\(a,b< c\)的情况:

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

    对于每个\(j\)只有\(i > \lfloor\frac{cj+c-b-1}{a}\rfloor\)时会产生\(1\)的贡献;

    \[\begin{aligned}原式 & =\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}\]

  2. \(g(a,b,c,n)\)

    同样,首先考虑\(a,b\geq c\)的情况:

    \(\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+6)}{2}\)

    \[\begin{aligned}原式 & =\sum_{i=0}^n i\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\bmod c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\bmod c)}{c}\rfloor\\ & =\sum_{i=0}^n i^2\lfloor\frac{a}{c}\rfloor+\sum_{i=0}^n i\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor\\ & =\frac{n(n+1)(2n+6)}{2}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor+g(a\bmod c,b\bmod c,c,n)\end{aligned}\]

    这样就转化成了\(a,b< c\)的情况:

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

    对于每个\(j\)只有\(i > \lfloor\frac{cj+c-b-1}{a}\rfloor\)时会产生\(i\)的贡献,是一个等差数列;

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

  3. \(h(a,b,c,n)\)

    同样,首先考虑\(a,b\geq c\)的情况:

    \[\begin{aligned}原式 & =\sum_{i=0}^n\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\bmod c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\bmod c)}{c}\rfloor^2\\ & =\sum_{i=0}^n(\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\bmod c))i}{c}\rfloor+\lfloor\frac{\lfloor\frac{b}{c}\rfloor\cdot c+(b\bmod c)}{c}\rfloor)^2\\ & =\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)^2+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2+2\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor\\ & =\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i)^2+\sum_{i=0}^n\lfloor\frac{b}{c}\rfloor^2+\sum_{i=0}^n2\lfloor\frac{a}{c}\rfloor i\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2+\\ & \quad 2\lfloor\frac{a}{c}\rfloor \sum_{i=0}^ni\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+2\lfloor\frac{b}{c}\rfloor\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor\\ & =\frac{n(n+1)(2n+6)}{2}\lfloor\frac{a}{c}\rfloor^2+(n+1)\lfloor\frac{b}{c}\rfloor^2+n(n+1)\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+h(a\bmod c,b\bmod c,c,n)+\\ & \quad 2\lfloor\frac{a}{c}\rfloor g(a\bmod c,b\bmod c,c,n)+2\lfloor\frac{b}{c}\rfloor f(a\bmod c,b\bmod c,c,n)\end{aligned}\]

    这样就转化成了\(a,b< c\)的情况:

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

    \[\begin{aligned}原式 & =\sum_{i=0}^n(2\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j-\lfloor\frac{ai+b}{c}\rfloor)\\ & =\sum_{i=0}^n2\sum_{j=1}^{\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}[i > \lfloor\frac{cj+c-b-1}{a}\rfloor]-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)\\ & =nm(n+1)-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}\]

这样递归处理,复杂度和欧几里得算法一致。 边界条件:\(a=0\)时,返回\(0\)

作者

xqmmcqs

发布于

2018-01-09

更新于

2023-03-29

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×