类欧几里得算法

请大家注意：

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

学习背景

之前做了一道类欧＋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}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 监督学习应用：梯度下降
    【转载】线性代数基础知识 原文地址：http://blog.csdn.net/longxinchen_ml/art...
    刘卡卡爱吃烤土豆阅读 5,117评论 0赞 0
  • 不要去想北极熊！
    1987 美国哈佛大学社会心理学家丹尼尔·魏格纳（Daniel Wegner）进行了一项实验。他把实验对象分成3组...
    半半老爸阅读 6,357评论 1赞 2
  • 成长的路上有你也有我
    纷纷扰扰，花落花开，年复一年。看着儿子已经六岁了，幼儿园最后半学期是正在进行时了呀! 感叹时光匆匆，岁月流逝，好像...
    草蝶阅读 1,748评论 0赞 1
  • 悟老子
    如果人有大彻大悟者，老子是古往今来独一人。经过生活，再回首且能平静地看着世间的一切，这过来的轨迹就...
    易点阅读 1,495评论 0赞 0
  • 识花知草之婆婆纳
    一度曾把这小小的蓝花儿错认成勿忘我，直到在妹妹的带动下定了一年鲜花才发现勿忘我完全不是这样。 目前草地上的...
    米粒微光阅读 4,084评论 0赞 0