@TOC

数论

扩展欧几里得

ta用于解二元一次不定方程：\(a*x+b*y=c\) 我们先考虑解这个方程：\(a*x+b*y=gcd(a,b)\) 如果$gcd(a,b)|c$，那么方程有解，否则无解 怎么解呢？ 既然$$ax+by=gcd(a,b)$$成立，那么易证下面这个式子也应该成立： \(b*x_1+(a\%b)*y_1=gcd(a,b)\) 接下来可以一直迭代，直到$b_n=0$，这时不难发现：\(a_n=gcd(a,b)\) 于是我们找到了一组特殊解：\(x_n=1,y_n=0\) 这时我们要做的是以这组特殊解倒推上一组方程的一组解。 由开始的两个式子可以做一些特殊的变化： \(a*x+b*y=gcd(a,b)\) \(b*x_1+(a\%b)*y_1=gcd(a,b)\) \(→\) \(a*x+b*y=gcd(a,b)\) \(b_1*x+(a-\lfloor\frac{a}{b}\rfloor*b)*y_1=gcd(a,b)\) \(→\) \(a*x+b*y=gcd(a,b)\) \(a*y_1+b*(x_1-\lfloor\frac{a}{b}\rfloor*y_1)=gcd(a,b)\) 令$$x=y_1;y=x_1-\lfloor\frac\rfloor*y_1$$ 就得到了上一层的解； 再一直回溯上去就可以得到最开始的方程的一组解了； 代码（超级好写）：

int exgcd(ll &x,ll &y,ll a,ll b){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	ll g=exgcd(x,y,b,a%b);
	ll z=x;
	x=y;
	y=z-a/b*y;
	return g;
}

乘法逆元

如果让你求一个式子$a/b(mod c)$的结果，怎么办？ 这时需要乘法逆元。 定义一个数$x$在模$p$意义下的逆元为$inv_x$，可以记为$x^{-1}$。 满足$$x*inv_x=1(mod p)$$ 有三种求法：

1.费马小定理（最好写）

\(x^{p-1}=1(mod p)\) 左右同时乘以$x^{-1}$得到 \(x^{p-2}=x^{-1}(mod p)\) 然后直接快速幂即可求出逆元了 （费马小定理要求$p$为质数）

2.扩展欧几里得

求$$x*inv=1(mod p)$$ 中的$inv$ 可以把式子等价的写成 \(x*inv+p*y=1(mod p)\) 是不是很眼熟，套一下$exgcd$的板子就行了 （这里的$p$不一定是质数，只要满足$x$和$p$互质保证有解即可）

3.递推

可以$O(n)$地求出$1-n$中每个数在模$p$意义下的逆元 首先$$11^{-1}=1(mod p)$$ 即$inv_1=1$ 然后考虑把模数$p$化成如下形式 \(p=k*x+b\) 其中$$k=\lfloor\frac\rfloor$$$$b=p%x$$ 显然$$kx+b=0(mod p)$$ 两边同时乘以$x^{-1}$和$b^{-1}$得到$$k*b^{-1}+x^{-1}=0(mod p)$$ 由于$b$小于$x$，那么$b^{-1}$一定已经已知 因此可以递推了：

inv[i]=(p-p/i)*inv[p%i]%p;

注意在$-p/i$前面加一个$p$是为了方便运算，防止复杂的负数取模

（扩展）中国剩余定理

（扩展）卢卡斯定理

莫比乌斯反演

杜教筛

函数

快速傅里叶变换（Fast Fourier Transformation）

快速数论变换（Number Theoretic Transforms）

快速沃尔什变换（Fast Walsh Transform）

矩阵

矩阵乘法及快速幂

矩阵加速

计算几何（没学）

数学专题——学习笔记

原文：https://www.cnblogs.com/hzyhome/p/11658227.html