数学-数论-类欧几里得算法

Posted by

定义

给定\(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\ mod\ c)\),\(b\)同理。
    \(\begin{aligned}原式 & =\sum_{i=0}^n\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\ mod\ c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\ mod\ 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\ mod\ c)i+(b\ mod\ 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\ mod\ c)i+(b\ mod\ c)}{c}\rfloor\\ & =\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}原式 & =\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\ mod\ c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\ mod\ 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\ mod\ c)i+(b\ mod\ 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\ mod\ c,b\ mod\ 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\ mod\ c))i+\lfloor\frac{b}{c}\rfloor\cdot c+(b\ mod\ c)}{c}\rfloor^2\\ & =\sum_{i=0}^n(\lfloor\frac{(\lfloor\frac{a}{c}\rfloor\cdot c+(a\ mod\ c))i}{c}\rfloor+\lfloor\frac{\lfloor\frac{b}{c}\rfloor\cdot c+(b\ mod\ 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\ mod\ c)i+(b\ mod\ c)}{c}\rfloor^2+2\sum_{i=0}^n(\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor)\lfloor\frac{(a\ mod\ c)i+(b\ mod\ 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\ mod\ c)i+(b\ mod\ c)}{c}\rfloor^2+\\ & \quad 2\lfloor\frac{a}{c}\rfloor \sum_{i=0}^ni\lfloor\frac{(a\ mod\ c)i+(b\ mod\ c)}{c}\rfloor+2\lfloor\frac{b}{c}\rfloor\sum_{i=0}^n\lfloor\frac{(a\ mod\ c)i+(b\ mod\ 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\ mod\ c,b\ mod\ c,c,n)+\\ & \quad 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)\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\)。

One comment

Leave a Reply

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