类欧几里得算法

作者: Tacmon_old | 来源:发表于2020-01-19 16:45 被阅读0次

类欧几里得算法
扩展欧几里得算法
算法学习(2)----丢番图方程
扩展欧几里德算法
第三周第四天代码
扩展欧几里得算法
GCD欧几里得算法 & EXGCD扩展欧几里得算法
组合数求解
拓展欧几里得算法
欧几里得算法

请大家注意：

因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。

学习背景

之前做了一道类欧＋ $Stern-Brocot\ Tree$ 二分的题目，就学一下。

问题模型

求
$f(n,a,b,c) = \sum_{i=0}^{n} \left\lfloor \frac{ai+b}{c} \right\rfloor$
$g(n,a,b,c) = \sum_{i=0}^{n} i \left\lfloor \frac{ai+b}{c} \right\rfloor$
$h(n,a,b,c) = \sum_{i=0}^{n} \left(\left\lfloor \frac{ai+b}{c} \right\rfloor\right)^2$

解法推导

为了方便，我们设 $m= \left\lfloor \frac{na+b}{c} \right\rfloor$
注意，因为取模符号太宽了，所以用C++的"%"来表示取模。

（一） $f(n,a,b,c)$

第一种情况： $a<c且b<c$
这个可以直接推导，比较简单。
$\begin{align} f(n,a,b,c) &= \sum_{i=0}^{n} \left\lfloor \frac{ai+b}{c} \right\rfloor \\ &= \sum_{i=0}^{n} \sum_{j=0}^{n} \left[j < \left\lfloor \frac{ai+b}{c}\right\rfloor \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} \left[j < \left\lfloor \frac{ai+b}{c}\right\rfloor \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} \left[j < \left\lceil \frac{ai+b-c+1}{c}\right\rceil \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} \left[j < \frac{ai+b-c+1}{c} \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} \left [cj < ai+b-c+1 \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} \left[ i> \frac{cj+c-b-1}{a} \right] \\ &= \sum_{j=0}^{m-1} n - \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \\ &= nm - \sum_{j=0}^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \\ &= nm - f(m - 1, c, c - b - 1, a) \end{align}$
第二种情况： $a\geq c且b\geq c$
这时候我们只要将 $\left\lfloor \frac{ai+b}{c} \right\rfloor$ 拆开，就是：
$\begin{align} f(n,a,b,c) &= \sum_{i=0}^{n} \left\lfloor \frac{ai+b}{c} \right\rfloor \\ &= \sum_{i=0}^{n} \left( \left\lfloor \frac{(a % c)i+(b % c)}{c} \right\rfloor + i \left\lfloor \frac{a}{c} \right \rfloor + \left\lfloor \frac{b}{c} \right\rfloor \right) \\ &= \frac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + n \left\lfloor \frac{b}{c} \right\rfloor + \sum_{i=0}^{n} \left\lfloor \frac{(a % c)i+(b % c)}{c} \right\rfloor \end{align}$

（二） $g(n,a,b,c)$

第二类和第一类比较类似，就写得简单一点。

第一种情况： $a<c且b<c$
$\begin{align} g(n,a,b,c) &= \sum_{i=0}^{n} i \left\lfloor \frac{ai+b}{c} \right\rfloor \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} i \left[ \left\lfloor\ \frac{ai+b}{c} \right\rfloor > j \right] \\ &= \sum_{j=0}^{m-1} \sum_{i=0}^{n} i \left[ i > \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right] \\ &= \frac{mn(n+1)}{2} - \sum_{j=0}^{m-1} \frac{\left\lfloor \frac{cj+c-b-1}{a} \right\rfloor (\left\lfloor \frac{cj+c-b-1}{a} \right\rfloor+1)}{2} \\ &= \frac{mn(n+1)}{2} - \frac{1}{2} \sum_{j=0}^{m-1} \left( \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \right)^2 - \frac{1}{2} \sum_{j=0}^{m-1} \left\lfloor \frac{cj+c-b-1}{a} \right\rfloor \\ &= \frac{mn(n+1)}{2} - \frac{1}{2}h(n,c,c-b-1,a) - \frac{1}{2}f(n,c,c-b-1,a) \end{align}$
第二种情况： $a\geq c且b\geq c$
这个也和 $f(n,a,b,c)$ 类似，直接给出结论了：
$g(n,a,b,c) = \frac{n(n+1)(2n+1)}{6}\left\lfloor \frac{a}{c} \right\rfloor + \frac{n(n+1)}{2}\left\lfloor \frac{b}{c} \right\rfloor + g(n,a \% c, b \% c, c)$

（三） $h(n,a,b,c)$

因为这里涉及到了平方，所以我们考虑用一种求和式表示平方。
$n^2 = 2\sum_{i=0}^{n} i - n$
之后，有如下推导：

第一种情况： $a<c且b<c$
$h(n,a,b,c) = \sum_{i=0}^{n} \left( 2\sum_{j=0}^{\left \lfloor\frac{ai+b}{c}\right\rfloor}j - \left\lfloor\frac{ai+b}{c}\right\rfloor \right)$
之后，就用与求 $f$ 和 $g$ 类似的方法，得到：
$h(n,a,b,c) = nm(m+1) - 2g(m-1,c,c-b-1,a) - 2f(m-1,c,c-b-1,a) - f(n,a,b,c)$
第二种情况： $a\geq c且b\geq c$
对于这个，就直接将三项式暴力拆开，就有：
$\begin{align} h(n,a,b,c) = \left\lfloor \frac{a}{c} \right\rfloor^2 \times \frac{n(n+1)(2n+1)}{6} + \left\lfloor \frac{b}{c} \right\rfloor^2 \times (n+1) + \left\lfloor \frac{a}{c} \right\rfloor \times \left\lfloor \frac{b}{c} \right\rfloor \times n(n+1) + h(n,a \% c, b \% c, c) + 2\left\lfloor \frac{a}{c} \right\rfloor g(n,a \% c, b \% c, c) + 2\left\lfloor \frac{b}{c} \right\rfloor f(n,a \% c, b \% c, c) \end{align}$

类欧几里得算法
请大家注意：因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式...
扩展欧几里得算法
资料欧几里得算法扩展欧几里得算法扩展欧几里得算法应用欧几里得算法欧几里得算法用于求两个数的最大公约数证...
算法学习(2)----丢番图方程
之前一篇随笔"算法学习(1)----扩展欧几里得算法"记录了对朴素欧几里得算法和扩展欧几里得算法的学习和认识...
扩展欧几里德算法
扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）...
第三周第四天代码
第三周第四天分数类，运算符重载，欧几里得算法学生类，文档注释，属性的分类一张牌类一副牌类玩家类调用这些...
扩展欧几里得算法
扩展欧几里得算法（Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展...
GCD欧几里得算法 & EXGCD扩展欧几里得算法
欧几里得算法欧几里得算法 (Euclidean algorithm) 是用来解决最大公约数问题的，通常采用辗转相除...
组合数求解
扩展欧几里得算法原理求解逆元的方法（本文采用扩展欧几里得算法进行求解）求组合数的两种方法Lucas定理
拓展欧几里得算法
问题求线性同余方程ax+by=c的整数解思路首先介绍下欧几里得算法的原理，众所周知，欧几里得算法是辗转相除法...
欧几里得算法
欧几里得算法介绍概念欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和...