记录一些自己可能会忘数学定理 & 一些喜欢的题单

老是很多数论定理和证明过程记不清, 记录一下.

---

威尔逊定理

若 $p$ 为质数，则 $(p-1)! \equiv -1 \pmod{p}$

拉格朗日定理

若 $H$ 是 $G$ 的一个子群，则 $|H|$ 整除 $|G|$ ，且 $|G| = [G:H]|H|$
$|G|$ 表示群大小，$[G:H]$ 表示 $H$ 在 $G$ 中左陪集的数量

欧拉反演
$\sum\limits_{d|n}{\varphi(d)} = n$
简单证明
$f(n) = \sum\limits_{d|n}{\varphi(d)}$
先证 $f$ 为积性函数
此处 $n$，$m$ 互质

$$f(n) \cdot f(m) = \sum\limits_{i|n}{\varphi(i)} \sum\limits_{j|m}{\varphi(j)} = \sum\limits_{i|n}{\sum\limits_{i|m}{\varphi(i)\varphi(j)}} = \sum\limits_{i|n}{\sum\limits_{j|m}{\varphi(ij)}} = \sum\limits_{d|nm}{\varphi(d)} = f(nm)$$

此处 $p$ 为质数

$$f(p^k) = \varphi(1)+\varphi(p)+\varphi(p^2)+ \cdots + \varphi(p^k) = 1+(p-1)+(p^2-p)+ \cdots + (p^k-p^{k-1}) = p^k$$ $$f(n) = f(p_1^{k_1})\cdot f(p_2^{k_2}) \cdots f(p_m^{k_m}) = p_1^{k_1}p_2^{k_2} \dots p_m^{k_m} = n$$

证毕

欧拉反演

$$\sum\limits_{i=1}^n{gcd(i,n)} = \sum\limits_{d|n}{\frac{n}{d}\varphi(d)}$$

简单证明

$$gcd(i,j) = \sum\limits_{d|gcd(i,j)}{\varphi(d)} = \sum\limits_{d|i}{\sum\limits_{d|j}\varphi(d)}$$ $$\sum\limits_{i=1}^n{gcd(i,n)} = \sum\limits_{i=1}^n{\sum\limits_{d|i}{\sum\limits_{d|n}{\varphi(d)}}} = \sum\limits_{d|n}{\sum\limits_{i=1}^n{\sum\limits_{d|i}{\varphi(d)}}} = \sum\limits_{d|n}{\frac{n}{d}\varphi(d)}$$

莫比乌斯反演

$$\sum\limits_{d|n}\mu(d) = [n == 1]$$

莫比乌斯反演
若 $f(n) = \sum\limits_{d|n}g(d)$
则有 $g(n) = \sum\limits_{d|n}{\mu(d)f(\frac{n}{d})}$

莫比乌斯反演
若 $f(n) = \sum\limits_{n|d}{g(d)}$
则有 $g(n) = \sum\limits_{n|d}{\mu(\frac{d}{n})f(d)}$

辛普森公式

$$\int_{L}^{R}{f(x) dx} \approx \frac{(R-L)(f(L)+f(R)+4f(\frac{L+R}{2}))}{6}$$

用二次函数来拟合原函数，再化简

伯努力数递推公式

$$B_n = -\frac{1}{n+1}\sum_{i=0}^{n-1}{\binom{n+1}{i}B_i}$$

自然幂数求和

$$\sum_{i=1}^{n}{i^m}=\frac{1}{m+1}\sum_{j=0}^{m}{\binom{m+1}{j}B_jn^{m-j+1}}$$

也可以用拉格朗日插值 $\mathcal{O}(n^2)$ 求,这是一个 $m+1$ 次多项式,可以解除系数

inline void mul(int *f,int deg,int opt) {
	for (register int i = deg+1;i >= 1;--i)tmp[i] = f[i],f[i] = f[i-1];
	for (register int i = 1;i <= deg+1;++i)
		f[i] = (f[i]+1ll*opt*tmp[i]%mod)%mod;
	return;
}
inline void div(int *f,int *g,int deg,int opt) {
	for (register int i = 1;i <= deg;++i)tmp[i] = f[i];
	for (register int i = deg-1;i >= 1;--i)
		g[i] = tmp[i+1],tmp[i] = (tmp[i]-1ll*tmp[i+1]*opt%mod+mod)%mod;
	return;
}
inline void Lagrange(int n) {
	fz[1] = 1;
	for (register int i = 1;i <= n;++i)mul(fz,i,(mod-x[i])%mod);
	for (register int i = 1;i <= n;++i) {
		int fenmu = 1;
		for (register int j = 1;j <= n;++j)
			if (i ^ j)fenmu = 1ll*fenmu*(x[i]-x[j]+mod)%mod;
		div(fz,fm,n+1,-x[i]);
		fenmu = 1ll*y[i]*power(fenmu,mod-2)%mod;
		for (register int j = 1;j <= n;++j)
			a[j] = (a[j]+1ll*fenmu*fm[j]%mod)%mod;
	}
	return;
}

范德蒙德卷积

$\sum\limits_{i=0}^{k}{\binom{n}{i} \binom{m}{k-i} } = \binom{n+m}{k}$

$\sum\limits_{i=1}^{n}{\binom{n}{i} \binom{n}{i-1}} = \binom{2n}{n-1}$

$\sum\limits_{i}{\binom{a-i}{n} \binom{i}{m}} = \binom{a+1}{n+m+1}$

位运算的性质

$i+j = (i \operatorname{and} j)+(i \operatorname{or} j)$

异或的性质

对于 $i < j < k$ , 有 $i \oplus k \geqslant min(i \oplus j,j \oplus k)$ .
$i \oplus j \geqslant \left| i-j \right|$
$\exists k < 2 \left| i-j \right|$ , $(i+k) \oplus (j+k) = \left| i-j \right|$

三点面积公式

$$\left| \begin{array}{cccc} x1 & y1 & 1\\ x2 & y2 & 1\\ x3 & y3 & 1 \end{array} \right| = \frac{1}{2}\left| x_1 y_2 + x_2 y_3 + x_3 y_1 - x_2 y_1 - x_3 y_2 - x_1 y_3\right|$$

单位根反演

$$\forall k,[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}{\omega_n^{ik}}$$

简单证明, 首先当 $n|k$ 时, $\omega_n^{ik}=\omega_n^0=1$ , 所以原式等于 $1$ .

否则是等比数列求和, $\dfrac{1}{n}\dfrac{\omega_n^{nk}-\omega_n^0}{\omega_n^k-1}=0$ .

加入我们要算某个多项式的特定倍数的系数和.

也就是要求这个, $\large{\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor}{[x^{ik}]f(x)}}$ .

$$\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor}{[x^{ik}]f(x)}\\ =\sum_{i=0}^n{[k|i][x^i]f(x)}\\ =\sum_{i=0}^{n}{[x^i]f(x)\frac{1}{k}\sum_{j=0}^{k-1}{\omega_k^{ji}}}\\ =\frac{1}{k}\sum_{i=0}^{n}{a_i\sum_{j=0}^{k-1}\omega_k^{ij}}\\ =\frac{1}{k}\sum_{j=0}^{k-1}{\sum_{i=0}^{n}{a_i(\omega_k^j)^i}}\\ =\frac{1}{k}\sum_{j=0}^{k-1}{f(\omega_k^j)}$$

---

srf01

srf02

srf03

srf04

srf05