复习的时候发现已经忘得差不多了。。。
一些等式
a≤?bc??ac≤ba≥?bc??ac≥ba?bc??ac>b(4)(4) a ≤ ? b c ? ? a c ≤ b a ≥ ? b c ? ? a c ≥ b a < ? b c ? ? a c < b a > ? b c ? ? a c > b
记住有等号则符号和大小与号一致，否则相反即可。
【类欧几里得算法总结】
?bc?=?b?c+1c??bc?=?b+c?1c?(5)(5) ? b c ? = ? b ? c + 1 c ? ? b c ? = ? b + c ? 1 c ?
可以和上面几个等价关系一起用。
类欧几里得
∑i=0n?ai+bc?=======∑i=0n∑j=0?ai+bc??11∑j=0?an+bc??1∑i=0n[j?cj+c?b?1a?]∑j=0?an+bc??1[n??cj+c?b?1a?]n??an+bc??∑j=0?an+bc??1[?cj+c?b?1a?](6)(6) ∑ i = 0 n ? a i + b c ? = ∑ i = 0 n ∑ j = 0 ? a i + b c ? ? 1 1 = ∑ j = 0 ? a n + b c ? ? 1 ∑ i = 0 n [ j < ? a i + b c ? ] = ∑ j = 0 ? a n + b c ? ? 1 ∑ i = 0 n [ j < ? a i + b ? c + 1 c ? ] = ∑ j = 0 ? a n + b c ? ? 1 ∑ i = 0 n [ c j < a i + b ? c + 1 ] = ∑ j = 0 ? a n + b c ? ? 1 ∑ i = 0 n [ i > ? c j + c ? b ? 1 a ? ] = ∑ j = 0 ? a n + b c ? ? 1 [ n ? ? c j + c ? b ? 1 a ? ] = n ? ? a n + b c ? ? ∑ j = 0 ? a n + b c ? ? 1 [ ? c j + c ? b ? 1 a ? ]
递归下去即可。
扩展类欧几里得 其实欧几里得还有几类扩展，因为运用不多，所以我没学，具体可以看:传送门
实数类欧几里得 BZOJ3817
大概是给你一条从原点出发直线（斜率为 r√r ）的直线下方整点的个数。迭代方法类似，不过斜率要单独记录。具体可以看:传送门
注意这种方法只对于直线没有经过整点的方法适用。经过整点可能需要一点讨论。
