大致记录一下ICPC中常见的自己比较容易忘记的数学结论.
-
勾股数定理
对于$$a^2+b^2 = c^2$$- $$a = m^2 – n^2 $$
- $$b = 2mn $$
- $$c = m^2 + n^2 $$
- $$gcd(n,m) = 1$$
- $$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) - gcd(b,p)=1 那么 a = b*x (mod p) 只有一个0<=x<p的解
- φ是欧拉函数,表示< =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。
-
A^x = A^(x % Phi(C) + Phi(C)) (mod C) 其中phi是欧拉函数
证明参见师父的博客http://hi.baidu.com/aekdycoin/blog/item/b6f1762565bb403fc8955908.html - 在数论上的一条欧拉公式 A^Phi(C)=1 (mod C) 前提是:(A,C)=1
-
Fib数列模p的循环。
1) p = 5, 暴力
2) 循环可能满足
a) 是P – 1的因子
b) 是2P + 2 的因子……
c) 就是P……
- $$gcd(Fib_x, Fib_y) = Fib_{gcd(x, y)}$$
-
-
一个数可以写成不相邻的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 - ( abs(a + b) + abs(a – b) ) / 2 = max( abs(a) , abs(b) ) 当+变为max的时候,往往就能定义dp的状态了。
- Erdős–Ginzburg–Ziv theorem 在mod n下,如果任意给定2n-1个数,一定存在一种取法,使得从中取n个出来的和为0
- $$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;
- 莫比乌斯反演公式得到
就算知道了这个还是没做对难倒各个教主的世纪数学难题“找最大的x,满足x的倍数在[L,R]区间里个数>=K” 跪烂= =
=.= 不知道这个的伤不起…
昨天cf div1的c么……
嗯=.=…找规律和数学都太弱了…其实知道这个以后只要不想当然认为单调就很好搞了…
我被cha了后反应到不单调,但是就想不到做法了 神坑。。。