题目大意
求:
前置技能
- 这个式子显然成立。
- 证明:
类欧几里得算法
这是一道类欧几里得的模板题,类欧几里得模板有三种形式:
下文为了方便,记$m=\lfloor\frac{ai+b}c\rfloor$。
推$f$式
先来看最简单的$f$推导。
- 若$a\ge c$或$b\ge c$
- $a,b\lt c$然后递归处理即可。
推$g$式
- 若$a\ge c$或$b\ge c$
- 若$a,b\lt c$发现这个$g$很麻烦,递归时需要用到$f$和$h$,因此不妨先看看$h$的推导。
推$h$式
- 若$a\ge c$或$b\ge c$
- 若$a,b\lt c$
此时我们需要用到前置技能中将平方展开成求和式的技巧。
本人采用下标从$1$开始的展开式,当然也可以使用下标从$0$开始的展开式,但与之前的递推式下标不对应,等会儿讲计算方法的时候就不好处理。
计算方法
- 按照递归式写出三个函数计算$f,g,h$并互相调用递归。
直观可行,但会有很多状态被重复计算,时间效率低下。 - 逐层递推
发现每一个$f/g/h(a,b,c,n)$仅与$f/g/h(c,c-b-1,a,m-1)$有关($h(a,b,c,n)$除外),因此我们不妨直接计算$f/g/h(c,c-b-1,a,m-1)$,然后计算出$f/g/h(a,b,c,n)$。
这样可以有效减少重复状态,时间效率优良。
时间复杂度分析
原式的值仅与$a,b,c$有关,与$n$关系不大。
若采用逐层递推的方法:
仅观察函数的第一/三维,即可发现每次从二元组$(a,c)$变为$(c,a\bmod c)$,因此与欧几里得算法类似,时间复杂度近似与欧几里得算法相同。
总结
类欧几里得算法的思想是将一个多项式转为求和式。
利用$\sum$的交换与除法的蜜汁性质对原式进行变形。
当原式变形到$\sum$与限制条件兼容时,即可去掉$\sum$直接计数。
目标是得到一个范围更小的递归式。
代码
1 |
|