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. 一个数可以写成不相邻的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
  9. ( abs(a + b) + abs(a – b) ) / 2 = max( abs(a) , abs(b) ) 当+变为max的时候,往往就能定义dp的状态了。
  10. Erdős–Ginzburg–Ziv theorem 在mod n下,如果任意给定2n-1个数,一定存在一种取法,使得从中取n个出来的和为0
  11. $$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;
  12. 莫比乌斯反演公式得到 p0

加入对话

5条评论

  1. 就算知道了这个还是没做对难倒各个教主的世纪数学难题“找最大的x,满足x的倍数在[L,R]区间里个数>=K” 跪烂= =

留下评论

回复 edward_mj 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注