2019.8.19 集训笔记

讲数论,$tql$ !


数学

容斥原理

直接手玩画图都可以推出公式。

普通的容斥原理,求某一部分:

然后还有一种叫做 “线性容斥” 的一个公式,有什么用我不知道。。。。

题目以后有时间做。。。。。

裂项

不写了。

调和级数

这个其实真正来说对解题没什么用,但是一般对于计算复杂度比较有用。

定义:全不为 0 的等差数列的倒数数列叫调和数列。

所以如果碰到形如这样的式子来计算复杂度:

就等于:

其中 $C$ 是欧拉函数。

这些前段时间我在洛谷网校上课的时候写过。

高斯消元

消元其实和普通的二元一次方程的消元一样,只是把他规范化了。在 $OI$ 中还要注意精度问题,细节我懒得打~(其实我不会)

欧几里得

感觉上面这个一级标题听起来很 $nb \; \Uparrow \; \Uparrow$

$gcd$

最简单的辗转相除法,直接上代码:

1
2
3
4
inline int gcd (int a, int b) {
if (b == 0) return a;
return gcd (b, a % b);
}

因为每次至少减少一半,所以说最坏 $O(\log n)$ 。

扩展 $gcd$

我曾经被一道经典的题目 同余方程 吊打。。。。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×