数学基础整理

收纳一些天天忘的结论qwq

线性求逆元

• $in{v}_i=(p-\frac{p}{i})\times in{v}_{p\mathrm{mod}i}$

卡特兰数

• 组合数公式：$H_n=C_{2n}^n-C_{2n}^{n-1}$

• 递推式：$H_n=\frac{H_{n-1}(4n-2)}{n+1}$

欧拉函数

• $n=\sum _{d\mid n}\phi (d)$

• 欧拉定理：$\gcd (a,m)=1,a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

• 拓展欧拉定理：$a^b\equiv \{\begin{array}{l}{a}^{b\mathrm{mod}\phi (m)}\gcd (a,m)=1\\ a^b\gcd (a,m)\ne 1\wedge b<\phi (m)\\ a^{b\mathrm{mod}\phi (m)+\phi (m)}\gcd (a,m)\ne 1\wedge b\ge \phi (m)\end{array}$$(\mathrm{mod}m)$

数论分块

• 满足 $\lfloor \frac{n}{i}\rfloor =\lfloor \frac{n}{x}\rfloor$ 的最大 $x$ 等于 $\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$

莫比乌斯变换

• 两个数论函数 $f(n),g(n)$，若 $f(n)=\sum _{d\mid n}g(d)$，则 $g(n)=\sum _{d\mid n}f(d)\mu (\frac{n}{d})$

阶

使得 $a^n\equiv 1(\mathrm{mod}m)$ 成立的最小正整数 $n$ 叫做 $a$ 模 $m$ 的阶，符号 ${\delta }_m(a)$。

一些性质：

• $\forall a^n\equiv 1(\mathrm{mod}m),{\delta }_m(a)\mid n⟹{\delta }_m(a)\mid \varphi (m)$
• ${\forall }_{i,j\in [1,{\delta }_m(a)],i\ne j}{a}^i\not\equiv a^j(\mathrm{mod}m)$
• $\gcd (a,m)=1,{\delta }_m(a^k)=\frac{{\delta }_m(a)}{\gcd (k,{\delta }_m(a))}$

原根

若 $\gcd (a,m)=1,{\delta }_m(a)=\varphi (m)$，则 $a$ 是 $m$ 的原根。

• 判定定理：${\forall }_{p\mid \varphi (m)}{a}^{\frac{\varphi (m)}{p}}\not\equiv 1(\mathrm{mod}m)⟺a$ 是 $m$ 的原根；
• 存在定理：只有 $2,4,p^a,2p^a$ 才存在原根，其中 $p$ 为奇素数；
• 原根个数：若 $m$ 有原根，则其原根个数为 $\varphi (\varphi (m))$；
• $m$ 的最小原根 $g$ 不超过 $m^{\frac{1}{4}}$，所有其它原根均为 $g^k(\gcd (k,\varphi (m)=1))$。