Math Conclusion

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

  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. 一个数可以写成不相邻的Fibonacci数组成(整数的Fibonacci分解,是唯一的),即
    , (不会有相邻的1)
    From Beijing2008 Problem B:A simple stone game
  8. ( abs(a + b) + abs(a - b) ) / 2 = max( abs(a) , abs(b) ) 当+变为max的时候,往往就能定义dp的状态了。
  9. Erdős–Ginzburg–Ziv theorem 在mod n下,如果任意给定2n-1个数,一定存在一种取法,使得从中取n个出来的和为0
  10. p(n)为正整数加法划分的方案数。其中k为非零整数(可以是负的),并假定p(x < 0) = 0; p(0) = 1;
  11. 莫比乌斯反演公式得到 p0

加入对话

5条评论

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

留下评论

您的电子邮箱地址不会被公开。