OI数学专题笔记 - 4
OI数学专题笔记 - 4
容斥原理
现有 {A1,A2,⋯ ,An}\{A_1, A_2, \cdots, A_n\}{A1,A2,⋯,An} 总共 nnn 个集合，一直任意多个子集交集的大小，则所有集合并集的大小为：
\sum_{B\subset\{A_1, A_2, \cdots, A ...
BSGS代码
BSGS代码
在OI数学笔记三中，我写过BSGS算法，这里是代码。
123456789101112131415161718int z[1005];void bsgs(int a, int b, int p) { int sp = int(sqrt(p)); z[0] = 1; ...
组合数学习笔记
组合数学习笔记
定义:
排列：从 nnn 个元素中选取 rrr 个元素，当考虑顺序时，所有可能的方案一共有：
Anr=n!(n−m)!A_n^r = \frac{n!}{(n - m)!}
Anr=(n−m)!n!
组合：从 nnn 个元素中选取 rrr 个元素，当不计顺序时，所有可能的方案 ...
高精度加减乘模板
高精度加减乘模板
这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。
其中要注意的是高精度减法需要均为正数，且大数减小数。如何比较大小？模板里面重载了 <<< 运算符，可以直接比较大小。
修改结构体中的 WIDTH 与 BASE 可以达到修 ...
素数筛法及线性筛求积性函数值学习笔记
素数筛法及线性筛求积性函数值学习笔记
定义
快速求出 1 n1 ~ n1 n 中所有素数的方法。
埃氏筛
12345678bool not_prime[1005];memset(not_prime, 0, sizeof(not_prime));not_prime[1] = true;for ...
快速乘法
快速乘法
快速乘的名字是从快速幂抄过来的，事实上它比直接乘要慢。
思路和快速幂一样，对于 k×xk \times xk×x ，可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x2k×x+2k×x ，若 kkk 为奇数，则再加个 ...
OI数学专题笔记 - 3
OI数学专题笔记 - 3
积性函数
如果函数 fff 满足 gcd(a,b)=1gcd(a, b) = 1gcd(a,b)=1 时有 f(ab)=f(a)f(b)f(ab) = f(a)f(b)f(ab)=f(a)f(b) ，则 fff 叫做积性函数。
如果取消互质的条件则叫做完全积性函 ...
扩展欧几里得算法（ExGCD）代码
扩展欧几里得算法（ExGCD）代码
之前的数学笔记中讲过这个算法，所以这里把代码贴一下。
123456789101112int exgcd(int a, int b, int& x, int& y) { if(b == 0) { x = 1 ...
Miller-Rabin 素性测试代码
Miller-Rabin 素性测试代码
之前的笔记中讲过这个算法，所以在这里把代码贴一下。
123456789101112131415161718192021222324int prime[8] = {2, 3, 5, 8, 11, 13, 17, 37};bool mi ...
OI数学专题笔记 - 2
OI数学专题笔记 - 2
素数的定义和判定
定义
如果 ppp 只有 1 和 ppp 两个印子，则 ppp 为负数。
Miller-Rabin 素性测试
如果 nnn 为素数，取 a<na < na<n ，设 n−1=d×2rn - 1 = d \times 2^rn−1= ...