OI 知识总览 算法篇 之 数学

OI 复习 数学

一) 矩阵

用途

矩阵快速幂 (一般用于优化dp)

二) 质数

内容

1. 质数筛法
2. 分解质因数

三) 约数

内容

1. 最大公约数 (欧几里得算法)
2. 欧拉函数 (欧拉函数 学习笔记)

题目

1. 反素数
2. 余数之和
3. Hankson 的趣味题 (解题报告)

四) 同余

同余 学习笔记

内容

1. 欧拉定理
2. 扩展欧拉定理
3. 费马小定理
4. 乘法逆元
5. 扩展欧几里得算法 (求解一元二次方程)

五) 组合数学

内容

1. 排列组合
2. Stiring 数
3. Catalan 数
4. 容斥原理

六) 概率与期望

七) 博弈论