竞赛数学公式结论

这篇文章主要记录竞赛中的数学公式和结论

数列

Fibonacci

通项公式

• $f(n)=\frac{1}{\sqrt[]{5}}[(\frac{1+\sqrt[]{5}}{2})^n-(\frac{1-\sqrt[]{5}}{2})^n]$

递推式

• $f(n)=f(n-1)+f(n-2)$

数论性质

• $gcd(f(n),f(m))=f(gcd(n,m))$

排列组合

排列数

错位排列

若序列 $a$ 使得 $a_i\neq i$ 恒成立
则令组成该序列的不同方案数为 $D(n)$
则有：

• $D(n)=(n-1)[D(n-1)+D(n-2)]$ 其中 $D(1)=0\ $ $D(2)=1$

组合数

卢卡斯定理

• $C_m^n\equiv C_{m\ mod\ p}^{n\ mod\ p}\cdot C_{\lfloor{\frac{m}{p}}\rfloor}^{\lfloor{\frac{n}{p}}\rfloor}(mod\ p)$

概率论

期望

多个独立事件发生 件数 的期望

• $p_1+p_2+p_3+...+p_n$

数论

约数

正约数个数

令正整数 $x$ 的正约数个数为 $D(x)$
$x$ 的唯一分解形式为 $x=p_1^{x_1}\cdot p_2^{x_2}\cdot...\ \cdot p_n^{x_n}$
则有：

• $D(x)=(x_1+1)(x_2+1)...(x_n+1)$

质因数

质数之积

两个质数之积一定为合数，因为这两个数本身就可以作为因子

$n!$

质因子 $p$ 在 $n!$ 中出现的个数为 $\displaystyle \sum_{p^k\leqslant n}\lfloor \frac{n}{p^k}\rfloor$

int count(int x, int a){
	int sum = 0;
	while(x){
		sum += x / a;
		x /= a;
	}
	return sum;
}

若要求出区间 $\displaystyle\prod^r_{i = l}$ 中质因子 $p$ 的个数，只需要得出 $count(r)-count(l - 1)$ 的结果即可