类欧几里德

很不错的算法呢，就是式子有点长，但还是不难推的( ´･･)ﾉ(._.`)

类欧几里得算法

前置知识

数学技巧

顶底函数

前言

类欧几里德算法是由洪华敦在 2016 年冬令营营员交流中提出的内容，其本质可以理解为，使用一个类似辗转相除法来做函数求和的过程。

主要还是推式子🤔

正文

问题1

设

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

其中$a,b,c,n \in \mathbb{Z}$。

一眼不可做，似乎像数论分块，但又好像不太行的样子。

$a,b,c,n$之间的关系也没给，那就分情况吧

首先考虑第一种情况$a \ge c,b \ge c$，（也是最简单的一种情况）

此时式子可以进一步化简为 ：

$$\tag{1,2} \begin{aligned} f(a,b,c,n) &= \sum_{i=0}^n \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor \\ &= \sum_{i=0}^n \bigg\lfloor\frac{(\lfloor \frac{a}{c} \rfloor \times c +a \bmod c)i+\lfloor \frac{b}{c} \rfloor \times c +b \bmod c}{c} \bigg\rfloor \\ &= \sum_{i=0}^n \bigg(\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c}\rfloor +\bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor \bigg) \\ &=\sum_{i=0}^n \lfloor \frac{a}{c} \rfloor i+\sum_{i=0}^n \lfloor \frac{b}{c}\rfloor +\sum_{i=0}^n \bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\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}$$

此时我们把式子化为了一个含有$f$的递归式，接下来$a,b$必定会变得小于$c$，还需讨论另一种情况

$a < c,b< c$时，这时候也不能用上面的方法，🤔

利用枚举贡献的方法，将式子化为 ：

$$\tag{1,3} f(a,b,c,n)=\sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} 1$$

似乎什么都没有做的样子。。

需要进一步化简：

$$\tag{1,4} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} 1 = \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \bigg[j< \lfloor\frac{ai+b}{c} \rfloor \bigg]$$

改了第二层求和的上界，好像有点头绪了

现在限制我们的就是后面的条件表达式了，也许可以将转化为某种方便计算的形式:

$$\tag{1,5} \because j< \lfloor\frac{ai+b}{c} \rfloor \\ \therefore j\le \frac{ai+b}{c} -1 \\ \therefore jc\le ai+b-c \\ \therefore jc < ai+b-c+1\\ \therefore i>\frac{jc+c-b-1}{a} \\ \therefore i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor$$

这样的话原来的式子就变为了：

$$\tag{1,6} \begin{aligned} f(a,b,c,n) &= \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=0}^n \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=\lfloor\frac{jc+c-b-1}{a}\rfloor+1}^n1 \\ &=\sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} (n-\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor) \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1}n- \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1}\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \\ &= \lfloor\frac{an+b}{c} \rfloor n-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1) \end{aligned}$$

将$\lfloor\frac{an+b}{c} \rfloor$设为$m$再整理一下，又得到一个递归式：

$$\tag{1,7} f(a,b,c,n)=mn-f(c,c-b-1,a,m-1)$$

综上（1,2）（1,6）：

$$\tag{1,8} f(a,b,c,n)= \left\{ \begin{aligned} & \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) &a\ge c\vee b \ge c\\ &\lfloor\frac{an+b}{c} \rfloor n-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1) &a<c\land b<c \end{aligned} \right.$$

可以在$O(\log n)$时间内求出。

问题2

设

$$\tag{2,1} g(a,b,c,n)= \sum_{i=0}^n i \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor$$

其中$a,b,c,n \in \mathbb{Z}$。

上个问题的升级版，（不就是多了个$i$嘛，别骂了别骂了)

接着分情况，$a\ge c,b\ge c$时：

$$\tag{2,2} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^n i \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor \\ &= \sum_{i=0}^n i \bigg\lfloor\frac{(\lfloor \frac{a}{c} \rfloor \times c +a \bmod c)i+\lfloor \frac{b}{c} \rfloor \times c +b \bmod c}{c} \bigg\rfloor \\ &= \sum_{i=0}^n i \bigg(\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c}\rfloor +\bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor \bigg) \\ &=\sum_{i=0}^n \lfloor \frac{a}{c} \rfloor i^2+\sum_{i=0}^n \lfloor \frac{b}{c}\rfloor i +\sum_{i=0}^n \bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor i \\ &= \frac{n(n+1)(2n+1)}{6} \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<c,b<c$ 时，枚举贡献将式子化为：

$$\tag{2,3} g(a,b,c,n)=\sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} i$$

改变上界：

$$\tag{2,4} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} i = \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} i \bigg[j< \lfloor\frac{ai+b}{c} \rfloor \bigg]$$

转化条件表达式：

$$\tag{2,5} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} i \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=0}^n i \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=\lfloor\frac{jc+c-b-1}{a}\rfloor+1}^n i \\ \end{aligned}$$

设$k=\lfloor\frac{jc+c-b-1}{a}\rfloor,m=\lfloor \frac{an+b}{c}\rfloor$，接着化简：

$$\tag{2,6} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^{m-1}\sum_{k+1}^ni \\ &= \sum_{i=0}^{m-1}\frac{(n-k)(n+k+1)}{2} \\ &= \sum_{i=0}^{m-1}\frac{n^2+n-k^2-k}{2} \\ &= \frac{1}{2}\bigg(mn^2+mn-\sum_{j=0}^{m-1}(\lfloor\frac{jc+c-b-1}{a}\rfloor)^2-\sum_{i=0}^{m-1}\lfloor\frac{jc+c-b-1}{a}\rfloor\bigg) \end{aligned}$$

。。。好像化的没问题啊，出现了一个没见过的平方，👀，先定义为$h(a,b,c,n)$吧，整理一下得：

$$\tag{2,7} g(a,b,c,n)= \left\{ \begin{aligned} & \frac{n(n+1)(2n+1)}{6} \lfloor \frac{a}{c} \rfloor+ \frac{n(n+1)}{2} \lfloor \frac{b}{c}\rfloor+g(a\bmod c,b\bmod c,c,n) & a\ge c\vee b\ge c \\ & \frac{1}{2}\bigg( \bigg\lfloor\frac{an+b}{c}\bigg\rfloor n(n+1) - h(c,c-b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)-f(c,c-b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)\bigg) & a<c \land b<c \end{aligned} \right.$$

接下来解决带平方的问题。

问题3

设

$$\tag{3,1} h(a,b,c,n)=\sum_{i=0}^n \bigg(\bigg\lfloor \frac{ai+b}{c}\bigg\rfloor \bigg)^2$$

其中$a,b,c,n \in \mathbb{Z}$。

上个问题还没有完全解决，需要解出$h(a,b,c,n)$，（不就多了个平方嘛，轻车熟路了，别打了别打了）

$$\tag{3,2} \begin{aligned} h(a,b,c,n) &= \sum_{i=0}^n \bigg(\bigg\lfloor\frac{ai+b}{c} \bigg\rfloor\bigg)^2\\ &= \sum_{i=0}^n \bigg(\bigg\lfloor\frac{(\lfloor \frac{a}{c} \rfloor \times c +a \bmod c)i+\lfloor \frac{b}{c} \rfloor \times c +b \bmod c}{c} \bigg\rfloor \bigg)^2\\ &= \sum_{i=0}^n \bigg(\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c}\rfloor +\bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor \bigg)^2 \\ \end{aligned}$$

手动多项式乘法！

原式变为：

$$\tag{3,3} h(a,b,c,n) =h(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n) +\left\lfloor\frac{a}{c}\right\rfloor^2\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor^2(n+1) +\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1)$$

接着考虑$a<c,b<c$的情况，设$k=\lfloor\frac{jc+c-b-1}{a}\rfloor,m=\lfloor \frac{an+b}{c}\rfloor$，

平方可以拆成：

$$\tag{3,3} n^2=2\frac{n(n+1)}{2}-n=\bigg( 2\sum_{i=0}^n i\bigg) -n$$

避免了出现$\sum \times \sum$，神一样的数学技巧

$$\tag{3,4} \begin{aligned} h(a,b,c,n) &=\sum_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor^2 \\ &=\sum_{i=0}^n\left[\left(2\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j \right)-\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\\ &=\left(2\sum_{i=0}^n\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j\right) -f(a,b,c,n)\\ \end{aligned}$$

接着化简前面的部分：

$$\tag{3,5} \begin{aligned} \sum_{i=0}^n\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j &=\sum_{i=0}^n\sum_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1}(j+1)\\ &=\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]\\ &=\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[i>k]\\ &=\sum_{j=0}^{m-1}(j+1)(n-k)\\ &=\frac{1}{2}nm(m+1)-\sum_{j=0}^{m-1}(j+1)\left\lfloor \frac{jc+c-b-1}{a} \right\rfloor\\ &=\frac{1}{2}nm(m+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1) \end{aligned}$$

整理一下：

$$\tag{3,6} h(a,b,c,n)= \left\{ \begin{aligned} &h(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n) +\left\lfloor\frac{a}{c}\right\rfloor^2\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor^2(n+1) +\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1) & a\ge c \vee b\ge c \\ & n\lfloor \frac{an+b}{c}\rfloor(\lfloor \frac{an+b}{c}\rfloor+1)-2g(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor-1)-2f(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor-1)-f(a,b,c,n) & a<c \land b<c \end{aligned} \right.$$

时间复杂度均为$O(\log n)$！

后寄

推完后人傻了😱😱😱，推$h$后半部分的时候照着OIWiki打的，我太菜了，呜呜呜~。