数论总集

卡特兰序列

\(C_{k}(m, n)\) 表示在网格中从 \((0,0)\) 走到 \((m,n)\) 时均不经过 \(y = x + k\) 的斜线即每时每刻满足 \(y < x + k\)

画图可得 \(C_{k}(m, n) = \binom{n+m}{m} - \binom{n+m}{m+k}\)

用法：任意前缀和不小于 \(-x\) 使用 \(C_x\) （左括号是 \(+1\))

反射容斥

学习博客

对称 ： \((a, b)\) 关于 \(y = x + k\) 的对称点为 \((b-k,a+k)\)

那么自然，对称 \(w\) 次 就是 \((b-wk,a+wk)\)

手玩之后递归一下就行

原根

\(\delta_m(a)\) 是 \(a\) 在\(\mod m\) 意义下最小的阶

即为 \(a^n \equiv 1 \pmod m\) 中最小的 \(n\)

（以下定理有一些数域的条件，但应该没有用吧）

• \(a,a^2,...,a^{\delta_m(a)} \mod m\) 两两互不相同
• \(a^n \equiv 1 \pmod m\) , 则 \(\delta(a) \mid n\)
• \((a,m)=(b,m)=1\) ，则 \(\delta_m(ab) = \delta_m(a)\delta_m(b)\)，的充要条件是 \((\delta_m(a),\delta_m(b)) = 1\)
• 若 \((a,m)\) ，\(\delta_m(a^k) = \frac{\delta_m(a)}{(\delta_m(a),k)}\)

定义原根 \(g\) ，满足 \(g^\varphi(m) \equiv 1 \pmod m\)

原根判定定理：

对于 \(m \ge 3\)，\((g,m)=1\)，则 \(g\) 是模 \(m\) 的原根的充要条件是，对于 \(\varphi(m)\) 的每个素因数 \(p\) 都有 \(g^\frac {\varphi(m)}{p} \not\equiv 1 \pmod m\)

原根个数：

若一个数 \(m\) 有原根，则其原根个数为 \(\varphi(\varphi(m))\)

原根存在定理：

\(m\) 存在原根当且 \(m=2,4,p^{\alpha},2p^{\alpha}\) ，其中 \(p\) 为奇素数，\(\alpha \in \N^*\)

最小原根的范围估计

反正大概是 \(O(n^{0.25+\epsilon})\)

中国剩余定理 CRT

\(x \equiv a_i \pmod{p_i}\) 其中 \(p_i\) 两两互质

那么 \(x\equiv \sum a_i \cdot \frac {P}{p_i} \cdot \operatorname{inv}(\frac{P}{p_i},p_i) \pmod {P=\prod p_i}\)

二项式反演

\(f_n \rightarrow\) 恰好用 \(n\) 个不同元素形成特定结构的方案数

\(g_n \rightarrow\) 从 \(n\) 个不同元素中选出 \(i \ge 0\) 个元素形成特定结构的总方案数

\(g_n = \sum\limits_{i=0}^n \binom{n}{i}f_i \rightarrow f_n = \sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{n-i}g_i\)

Legendre公式 & Kummer定理

Legendre 公式

对于 \(p \in prime\) ，\(v_p(n) \rightarrow\) \(n\) 标准分解后 \(p\) 的次数

• 显然 \(v_p(n!) = \sum\limits_{i=1}^\infty [\frac{n}{p^i}]\)

\(s_p(n) \rightarrow\) \(n\) 在 \(p\) 进制下的数位和

• \(v_p(n!) = \frac{n-s_p(n)}{p-1}\)

Kummer 定理

\(v_p(\binom{n}{m})=\frac{s_p(m) + s_p(n-m)-s_p(n)}{p-1}\)

同时也等于 \(p\) 进制下运算 \(n-m\) 的退位次数

\(v_p(\binom{n}{m_1,\dots,m_k})=\frac{\sum\limits_{i=1}^ks_p(m_i)-s_p(n)}{p-1}\)

*\(\binom{n+m}{m}\) 含 \(p\) 的幂次数为 \(\sum\limits_{1}^{\infty}([\frac{m+n}{p^i}]-[\frac{n}{p^i}]-[\frac{m}{p^i}])\) \(\leftarrow\) 有用常见的

相当于 \(n+m\) 在 \(p\) 进制下的进位次数

斐波那契

\(f_0 = 1, f_1 = 1, f_i = f_{i-1}+f_{i-2}\)

\(f_if_{i-1}-f_{i+1}f_{i-2}=(-1)^i\)

\(f_ix+f_{i+1}y=k\) 通解为 \(x=k*(-1)^if_{i-1},y=k(-1)^{i+1}f_{i-2}\)