类欧几里德算法由洪华敦在 2016 年冬令营营员交流中提出的内容，其本质可以理解为，使用一个类似辗转相除法来做函数求和的过程。
这个式子和我们以前见过的式子都长得不太一样。带向下取整的式子容易让人想到数论分块，然而数论分块似乎不适用于这个求和。但是我们是可以做一些预处理的。
要加快一个和式的计算过程，所有的方法都可以归约为 贡献合并计算 。但你发现这个式子的贡献难以合并，怎么办？ 将贡献与条件做转化 得到另一个形式的和式。具体地，我们直接把原式的贡献变成条件：
现在多了一个变量 j ，既然算 i 的贡献不方便，我们就想办法算 j 的贡献。因此想办法搞一个和 j 有关的贡献式。这里有另一个家喻户晓的变换方法，笔者概括为限制转移。具体来说，在上面的和式中 n 限制 i 的上界，而 i 限制 j 的上界。为了搞 j ，就先把 j 放到贡献的式子里，于是我们交换一下 ij 的求和算子，强制用 n 限制 j 的上界。
这样做的目的是让 j 摆脱 i 的限制，现在 ij 都被 n 限制，而贡献式看上去是一个条件，但是我们仍把它叫作贡献式，再对贡献式做变换后就可以改变 ij 的限制关系。于是我们做一些放缩的处理。首先把向下取整的符号拿掉
最后一步，向下取整得到：
这是一个递归的式子。并且你发现 ac 分子分母换了位置，又可以重复上述过程。先取模，再递归。这就是一个辗转相除的过程，这也是类欧几里德算法的得名。
理解了最基础的类欧几里德算法，我们再来思考以下两个变种求和式：
接下来考虑 a<cb<c 的情况，令 m=\left\lfloor\frac{an+b}{c}\right\rfloor 。之后的过程我会写得很简略，因为方法和上文略同：
我们发现这个平方不太好处理，于是可以这样把它拆成两部分：
这样做的意义在于，添加变量 j 的时侯就只会变成一个求和算子，不会出现 \sum\times \sum 的形式：
接下来考虑化简前一部分：
在代码实现的时侯，因为 3 个函数各有交错递归，因此可以考虑三个一起整体递归，同步计算，否则有很多项会被多次计算。这样实现的复杂度是 O(\log n) 的。