类欧几里得算法

Ztemily 发布于

类欧几里得算法

用于解一些神奇式子，形如：

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

$ {g(a,b,c,d)=\sum\limits_{i=0}^{n}i*\lfloor{\frac{ai+b}{c}}\rfloor} $

$ {h(a,b,c,d)=\sum\limits_{i=0}^{n}\lfloor{\frac{ai+b}{c}}\rfloor} ^2 $

其求值与求 $ gcd $ 所用的欧几里得算法类似，因此称之为类欧几里得算法。

求 $ f $ ：

我们希望可以递归计算，那么对于 $ a,b $ 关于 $ c $ 的大小关系去分类讨论。

1.$ a \geq c\ or\ b \geq c : $

我们考虑把烦人的向下取整化掉。

⌊ai+bc⌋→⌊(amod  c)∗i+bmod  cc⌋+⌊ac⌋∗i+⌊bc⌋\lfloor{ \frac {ai+b} {c} } \rfloor \to \lfloor{ \frac { (a \mod c) *i + b \mod c} {c} } \rfloor + \lfloor\frac{a}{c}\rfloor *i + \lfloor\frac{b}{c}\rfloor

那么有

f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i= 0}^{n}\left \lfloor \frac{ai + b}{c} \right \rfloor

=∑i=0n⌊(⌊ac⌋c+amod  c)i+⌊bc⌋c+bmod  cc⌋=\sum_{i = 0}^{n}\left \lfloor \frac{(\left \lfloor \frac{a}{c} \right \rfloor c +a\mod {c})i + \left \lfloor \frac{b}{c} \right \rfloor c + b\mod {c} }{c} \right \rfloor

=n(n+1)2⌊ac⌋+(n+1)⌊bc⌋+∑i=0n⌊(amod  c)i+bmod  cc⌋= \frac{n(n+1)}{2} \left \lfloor \frac{a}{c} \right \rfloor + (n + 1) \left \lfloor \frac{b}{c} \right \rfloor + \sum_{i = 0}^{n}\left \lfloor \frac{(a\mod {c})i + b \mod {c} }{c} \right \rfloor

2.a<c and b<ca<c \ and \ b<c

设

m=⌊an+bc⌋m=\lfloor\frac{an+b}{c}\rfloor

有

f(a,b,c,n)=∑i=0n∑j=1m[j≤⌊ai+bc⌋]f(a,b,c,n)=\sum\limits_{i=0}^{n}\sum\limits_{j=1}^{m}[j\le\lfloor\frac{ai+b}{c}\rfloor]

=∑i=0n∑j=0m−1[j+1≤⌊ai+bc⌋]=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[j+1\le\lfloor\frac{ai+b}{c}\rfloor]

=∑i=0n∑j=0m−1[i>⌊jc+c−b−1a⌋]=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[i>\lfloor\frac{jc+c-b-1}{a}\rfloor]

=∑j=0m−1n−⌊jc+c−b−1a⌋=\sum\limits_{j=0}^{m-1} n-\lfloor\frac{jc+c-b-1}{a}\rfloor

=nm−f(c,c−b−1,a,m−1)=nm-f(c,c-b-1,a,m-1)

即

f(a,b,c,n)=nm−f(c,c−b−1,a,m−1)f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)

即为

f(a,b,c,n)=n⌊ai+bc⌋−f(c,c−b−1,a,⌊ai+bc⌋−1)f(a,b,c,n)=n\lfloor\frac{ai+b}{c}\rfloor-f(c,c-b-1,a,\lfloor\frac{ai+b}{c}\rfloor-1)

就是a=c,c=amodca=c,c=amod c，递归边界为a=0a=0

那么

f(x)={n(n+1)2⌊ac⌋+(n+1)⌊bc⌋+∑i=0n⌊(amod  c)i+bmod  cc⌋,a≥c or b≥cf(a,b,c,n)=n⌊ai+bc⌋−f(c,c−b−1,a,⌊ai+bc⌋−1),a<c and b<cf(x)= \begin{cases} \frac{n(n+1)}{2} \left \lfloor \frac{a}{c} \right \rfloor + (n + 1) \left \lfloor \frac{b}{c} \right \rfloor + \sum_{i = 0}^{n}\left \lfloor \frac{(a\mod {c})i + b \mod {c} }{c} \right \rfloor,\quad a \geq c\ or\ b \geq c \\ f(a,b,c,n)=n\lfloor\frac{ai+b}{c}\rfloor-f(c,c-b-1,a,\lfloor\frac{ai+b}{c}\rfloor-1), \quad a<c \ and \ b<c \end{cases}

求gg：

和求 ff 类似套路，分类讨论即可

1.a≥c or b≥ca \ge c \ or \ b \ge c

有个小结论会用到

∑i=1ni2=n(n+1)(2n+1)6\sum\limits_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}

那么和求 ff 一样去掉整除即可

即

g(a,b,c,n)=g(amod  c,bmod  c,c,n)+n(n+1)(2n+1)6⌊ac⌋+n(n+1)2⌊bc⌋g(a,b,c,n)=g(a\mod c,b\mod c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor

2.a<c and b<ca<c \ and \ b<c

那么同样的，设

m=⌊an+bc⌋m=\lfloor\frac{an+b}{c}\rfloor

有

g(a,b,c,n)=∑i=0ni∑j=1m[j≤⌊ai+bc⌋]g(a,b,c,n)=\sum\limits_{i=0}^{n}i\sum\limits_{j=1}^{m}[j\le\lfloor\frac{ai+b}{c}\rfloor]

=∑i=0ni∑j=0m−1[i>⌊jc+c−b−1a⌋]=\sum\limits_{i=0}^{n}i\sum\limits_{j=0}^{m-1}[i>\lfloor\frac{jc+c-b-1}{a}\rfloor]

那么显然这里面有一个等差数列

得

g(a,b,c,n)=∑j=0m−1⌊(⌊jc+c−b−1a⌋+1+n)(n−⌊jc+c−b−1a⌋)2⌋g(a,b,c,n)=\sum\limits_{j=0}^{m-1}\lfloor\frac{(\lfloor\frac{jc+c-b-1}{a}\rfloor+1+n)(n-\lfloor\frac{jc+c-b-1}{a}\rfloor)}{2}\rfloor

=⌊mn(n+1)−f(c,c−b−1,a,m−1)−h(c,c−b−1,a,m−1)2⌋=\lfloor \frac{mn(n+1)-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1)}{2} \rfloor

即

g(a,b,c,n)=⌊⌊an+bc⌋n(n+1)−f(c,c−b−1,a,⌊an+bc⌋−1)−h(c,c−b−1,a,⌊an+bc⌋−1)2⌋g(a,b,c,n)= \lfloor \frac{\lfloor\frac{an+b}{c}\rfloor n(n+1)-f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-h(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)}{2} \rfloor

好了开始套娃
那么即为

g(x)={g(amod  c,bmod  c,c,n)+n(n+1)(2n+1)6⌊ac⌋+n(n+1)2⌊bc⌋,a≥c or b≥c⌊⌊an+bc⌋n(n+1)−f(c,c−b−1,a,⌊an+bc⌋−1)−h(c,c−b−1,a,⌊an+bc⌋−1)2⌋,a<c and b<cg(x)= \begin{cases} g(a \mod c,b \mod c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor, \quad a \ge c\ or\ b \ge c \\ \lfloor \frac{\lfloor\frac{an+b}{c}\rfloor n(n+1)-f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-h(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)}{2} \rfloor, \quad a<c \ and \ b<c \end{cases}

求hh：

推导过程：仁者见仁智者见智罢！

h(x)={h(amod  c,bmod  c,c,n)+2⌊bc⌋f(amod  c,bmod  c,c,n)+2⌊ac⌋f(amod  c,bmod  c,c,n)+n(n+1)(2n+1)6⌊ac⌋2+n(n+1)⌊ac⌋⌊bc⌋+(n+1)⌊bc⌋2,a≥c or b≥cn⌊an+bc⌋(⌊an+bc⌋+1)−2f(c,c−b−1,a,⌊an+bc⌋−1)−2g(c,c−b−1,a,⌊an+bc⌋−1)−f(a,b,c,n),a<c and b<ch(x)= \begin{cases} h(a \mod c,b \mod c,c,n)+2\lfloor\frac{b}{c}\rfloor f(a\mod c,b\mod c,c,n)+2\lfloor\frac{a}{c}\rfloor f(a\mod c,b\mod c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor\frac{a}{c}\rfloor^2+n(n+1)\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor^2, \quad a \ge c\ or\ b \ge c \\ n\lfloor\frac{an+b}{c}\rfloor(\lfloor\frac{an+b}{c}\rfloor+1)-2f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-2g(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-f(a,b,c,n), \quad a<c \ and \ b<c \end{cases}

终

Ztemily

Ztemily

此后如竟没有炬火，我们便是唯一的光。

6
0
1
NOTICE

新搭建的博客，欢迎来玩~

CATEGORYS
TAGS
OI