各种性质、定理
在这里记录一下做题中遇到的各种性质、定理，数论知识偏多，没有什么顺序，只是做到了就记录一下，不断更新。。
费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。
欧拉定理,（也称费马–欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:
欧拉函数
定义：用于计算 p(n)，比n小的所有与n互质的数。
计算公式：p(n)=n*(1-1/p1)*(1-1/p2)….*(1-1/pk)【p1,p2,pk都是n的素因子】
另：若n=p1^q1*p2^q2*…..*pk^qk
则，p(n)=(p1-1)*p1^(q1-1)*(p1-1)*p2^(q2-1)……*(pk-1)*pk^(qk-1)
性质：若m,n互质，φ(mn)=φ(m)φ(n)。当n为奇数时，φ(2n)=φ(n)
欧拉定理：
a,m互质，a^φ(m)≡1(mod m)
例：2,3互质，那么，2^2%3=1
推论：对于互质的数a、n，满足a^(φ(n)+1) ≡ a (mod n)
欧拉公式的延伸：小于n 与n互质的数的和 是euler(n)*n/2
多个数的最小公倍数 每个数分解因子 质因子最高次幂相乘之积
反素数 = 求约数最多的数 ：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.
性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4…..必然t1>=t2>=t3>=….
约瑟夫： f[1] = 0; f[i] = (f[i-1]+m)%i;
高次幂取模： a^b%c = a ^(b%eular(c)+eular(c)) % c。 eular（c)为欧拉函数
鸽巢原理 ： 若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。
若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。
推广定理 拉姆齐（Ramsey）定理: 又称拉姆齐二染色定理，是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
Pick定理是说，在一个平面直角坐标系内，如果一个多边形的顶点全都在格点上，那么这个图形的面积恰好就等于边界上经过的格点数的一半加上内部所含格点数再减一。
内切圆半径
直角三角形中
已知任意四面体（三棱锥）六条棱的棱长，求其体积。
不妨记同一顶点引出的三条棱棱长的平方分别为a，b，c，它们的对棱棱长的平方分别为d，e，f，则四面体的体积V满足：
V=
sqrt[ad(b+c+e+f-a-d)+be(a+c+d+f-b-e)+cf(a+b+d+e-c-f)-abf-bcd-cae-def)]/12
几何中的欧拉定理
多面体
多边形