#gan出博客评论过后开始正经写博客#
# 类欧几里得算法
欧几里得算法是计算 $(a,b)$,主要思想是 $(a,b)=(b\bmod a,a)$。这样保证了它的时间复杂度。
而类欧几里得算法,并不是像扩展欧几里得算法那样,它的正确性和欧几里得算法没有任何关系,只是它也有类似于 $(a,b)\to(b\bmod a,a)$ 这种操作,从而保证时间复杂度。
常见的 $3$ 种(然而我并不知道还有没有别的)可以用类欧几里得算法计算的式子有:
# 算法主体
- 计算 f
当然从看起来最简单的入手~
看到下取整,我们可以先把我们能够提取出的整数部分提取出来——当 $a\ge c$ 或 $b\ge c$ 时,令 $a’=a\bmod c$,$b’=b\bmod c$:
经过这一步后,有 $a<c$ 且 $b<c$。在此基础上继续:令 $m=\left\lfloor\frac{an+b}{c}\right\rfloor$
Warning!!! 公式恐惧者慎入
注意到上式的 $a,b$ 实际上是对 $c$ 取模得到的。因此,我们相当于完成了 $(a,c)\to(a\bmod c,c)\to(c,a\bmod c)$。根据欧几里得算法的证明,可以得到该算法在复杂度上的正确性。
> Addition
边界情况也就是 $a=0$,代入原式,可得 $f(0,b,c,n)=(n+1)\left\lfloor\frac bc\right\rfloor$。
- 计算 g
你会知道为什么要先讲 $f(a,b,c,n)$ 的……
和计算 f 一样的思路,先给 $a\bmod c$,$b\bmod c$:
> Addition
基本上每篇博客都说计算 $i^2$ 的前缀和是基本操作,然后不讲…… QwQ 然而我不会,太菜了
首先有 $(i+1)^3-i^3=3i^2+3i+1$,所以:
移项过后可得
然后就可以愉快的继续了~ 再考虑 $a<c$ 且 $b<c$ 的情况。仍然令 $m=\left\lfloor\frac{an+b}c\right\rfloor$,
可以看到这几个函数乱七八糟互相嵌套……但是复杂度还是正确的~
> Hint
别忘了 1/2!
- 计算 h
已经熟悉了的套路:
真是够麻烦的……
继续吧?然而发现因为有平方,不能按之前的方法把 $\left\lfloor\frac{ai+b}{c}\right\rfloor$ 拆成求和式,这时候就需要在 OI-wiki 上找一下骚操作了 awa:
为了公式好看一点,定义 $m_i=\left\lfloor\frac{ai+b}{c}\right\rfloor$。
这个式子意义何在?注意到 $\frac{m_i(m_i+1)}2$ 是 $1,…,m_i$ 的和。那么:
想办法处理前面的求和式:
> Hint
# 处的推导,可以考虑有多少个 $i$ 能够取到 $(j+1)$
怎么又套了另外的函数……看来这几个函数一起求 (!见代码)是被安排好了的
# 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
我觉得应该向 OI 界全力推广 OI-wiki ο(=•ω<=)ρ⌒☆