【数论】(所有的等于都是恒等)
- 费马小定理：p为质数
A^(p-1)=1 (mod p)
- 欧拉定理：p是任意自然数
A^phi(p)=1 (mod p)
费马小定理是欧拉定理的特殊情况
欧拉函数：phi(n)是少于n的数中与n互质的数的数目
求法：小学生容斥
减去含一个素数的，加上含两个素数的，减去含三个函数的……. N(1/1-1/p1-1/p2+1/p1*p1…….)
设R（s）=（1-1/p1）*R(S/n))
p为底数集合，a为指数集合
例子：15=3^1*5^1
Phi(15)=(3-1)*3^(1-1)*(5-1)*5^(1-1)=2*4=8
一个需要记住的结论
例题
- 素数判断
随机整数a,根据费马小定理判断a^(n-1)=1
4二次探测定理
若p是素数，x是一个整数，且x^2 mod p=1,那么x=1|x=-1(mod p)
一个质数不存在“非平凡平方根”
例：23^2=1(mod 66)
5.Miller_rabin
Miller-rabin是一个基于费马小和二次探测定理的一种有一定错误率的算法。
我们要尽可能的找能够判断这个数为合数的线索，
要么，它违背了费马小，要么它违背了二次探测（主）
如果他是从（-1）^2过来的，我无话可说，也无法判断是否为合数，但如果他是从别的数通过%p得来的，那么他就是是违背了二次探测定理，所以我们就可以就此判断他是合数
6.快速乘
11.同二进制快速幂
12. 2.65526进制快速幂
13. (a * b−(long long)floor((long double)a *b/m) * m + m)%m
人品算法，爆零自负自负
7.中国剩余定理
x在mod Bi时，其实只有一个式子与结果有关
就是：Ki*R/Bi(其它式子都包含Bi)
所以就会变成 Ki’*R/Bi=x (mod Bi),也就变成了裴蜀定理
8.欧几里得算法
Gcd(a,b)=gcd(b,a%b)
Gcd(a,b)*ab=lcm(a,b)
裴蜀定理：ax+by=m 有解当且仅当m是gcd(a,b)的倍数//
扩展欧几里得求同余方程
求得 x=y’,y=x’-a/by’，推到底，再顺着退回来
9.同余系
10.积性函数：如果一个数论函数f(x)满足对于任意的互质正整数n,m均有f(nm)=f(n)*f(m),称为积数函数
完全积性函数：如果一个数论函数f(x)满足对于任意的正整数n,m均有f(nm)=f(n)*f(m),称为完全积数函数（特）
常见积性函数
模n意义下的逆元INV（x）
欧拉函数 phi（x）
因数个数的函数
因数和函数
莫比乌斯函数 mu(x)
11.线性筛
If(i%prime[j]==0) break;
线性筛不仅可以O(n)的筛除所有的素数，还可以同时求出所有的积性函数，具体详见《贾志鹏线性筛》
例题：定情信物：
Ans=c(k,n)*2^(n-k)
N表示总维度，k表示所求元素的个数
线性筛求逆元，记录p出现了多少次
【高精度】
用class（类）来搞最好。
重定义函数+压位
【卷积】ci=sum k (ak*bi-k)
aàa’
bàb’
càc’ (傅里叶变换O(n))
a’与b’的卷积=c’ ,a与b的卷积=c
【Python】;
Import.math 数学函数
Import.sqrt(10);
Math.log(1,123)
甚至可以求虚数 import.sqrt(-1)
且用python写数据，输出的数据都是自带最快高精的。
具体的语句还需要具体的学习
【矩阵】