Math Conclusion

大致记录一下ICPC中常见的自己比较容易忘记的数学结论.

1. 勾股数定理
   对于$$a^2+b^2 = c^2$$
   1. $$a = m^2 – n^2 $$
   2. $$b = 2mn $$
   3. $$c = m^2 + n^2 $$
   4. $$gcd(n,m) = 1$$
   5. $$gcd(a,b,c) = 1$$

   同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾股数和三元对(m,n,k)一一对应。
   换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。
   并且k=1时，必须满足c%4==1才能分出来。
   (Fermat’s two-square theorem. A prime number with p=4n+1 can be written as the sum of two square numbers)

2. gcd(b,p)=1 那么 a = b*x (mod p) 只有一个0<=x<p的解
3. φ是欧拉函数，表示< =n的数里和n互质的数有多少个？ φ(n)=n*（1-1/p1)(1-1/p2)….(1-1/pk),其中p1、p2…pk为n的所有素因子。 比如：φ(12)=12*(1-1/2)(1-1/3)=4。
4. A^x = A^(x % Phi(C) + Phi(C)) (mod C) 其中phi是欧拉函数
   证明参见师父的博客http://hi.baidu.com/aekdycoin/blog/item/b6f1762565bb403fc8955908.html
5. 在数论上的一条欧拉公式 A^Phi(C)=1 (mod C) 前提是：(A,C)=1
6. Fib数列模p的循环。

   1) p = 5, 暴力

   2) 循环可能满足

   a) 是P – 1的因子

   b) 是2P + 2 的因子……

   c) 就是P……

7. $$gcd(Fib_x, Fib_y) = Fib_{gcd(x, y)}$$
8. 
   
   
9. 一个数可以写成不相邻的Fibonacci数组成(整数的Fibonacci分解，是唯一的)，即
   $$N = a_nF_n + a_{n-1}F_{n-1} + … + a_1F_1$$, $$a_i=0,1$$ （不会有相邻的1）
   From Beijing2008 Problem B：A simple stone game
10. ( abs(a + b) + abs(a – b) ) / 2 = max( abs(a) , abs(b) ) 当+变为max的时候，往往就能定义dp的状态了。
11. Erdős–Ginzburg–Ziv theorem 在mod n下，如果任意给定2n-1个数，一定存在一种取法，使得从中取n个出来的和为0
12. $$p(n) = \sum_k(-1)^{k-1}p(n – g_k) = \sum_k(-1)^{k-1}p(n – \frac{k*(3k-1)}{2})$$ p(n)为正整数加法划分的方案数。其中k为非零整数(可以是负的)，并假定p(x < 0) = 0; p(0) = 1;
13. 莫比乌斯反演公式得到