Basis
琪露诺的完美小学数学教室。
バカバカ。
不要怀疑我为什么起这种名字，我就是在钓鱼。
实际上就是方便背结论把一堆东西扔到一起。
数论
反素数：$p _ 1 = 2$，质数连续，指数不增，用就爆搜。
欧拉定理及扩展降低指数：
对于 $a \perp n$，有 $a ^ { p } \equiv a ^ { p \bmod \varphi ( n )} \pmod{n}$。
反之，若 $p \ge \varphi(n)$，有 $a ^ {p} \equiv a ^ {p\bmod \varphi (n)+\varphi(n)} \pmod {n}$
裴蜀定理：
$a _ 1 , a _ 2 , \cdots , a _ n$ 是不全为 $0$ 的整数。
则存在解 $x _ 1 , x _ 2 ,\cdots ,x _ n$ 使得：
$$\sum _ { i = 1 } ^ {n} a _ i x _ i = \gcd( a _ 1 , a _ 2,\cdots , a _ n )$$
类欧几里得：P5170
推导过程都是类似的（而且有些长）。
欧拉定理与费马小定理：
$$\forall a\perp n, a ^ {\varphi (n)} \equiv 1\pmod{n}$$
$$\forall a \perp n, n \in \mathcal {P}, a ^ n\equiv a \pmod {n}$$
线性求逆元：
$$i ^ {-1} \equiv - \lfloor p / i \rfloor ( p \bmod i ) ^ {-1} \pmod {p}$$
线性求任意 $n$ 个数的逆元：
前缀积这 $n$ 个数，记为 $s_n$，求其逆元，记为 $v_n$。由 $v _ n $ 可推得 $ v _ 1 , \cdots , v _ {n-1}$。
易知 $a _ i ^ {-1} =s _ { i - 1} v _ i$。
中国剩余定理：
对于 $m _ 1 ,\cdots , m _ k$ 两两互质，线性同余方程组：
$$
\begin{cases}
x \equiv a _ 1 \pmod { m _ 1 }
\\
\cdots
\\
x \equiv a _ k \pmod { m _ k }
\end{cases}
$$有解，且解可以构造出来。
令 $m=\prod _{ i = 1 } ^ { k } m _ i , M _ i = m / m _ i$，并求出 $M _ i$ 模 $m _ i $ 下的逆元 $ t _ i$。
则 $x = \sum _ {i = 1 } ^ {k} a _ i M _ i t _ i$ 是一个合法的解。该解可以在模 $m$ 的意义下任意变换。
扩展中国剩余定理：
只讨论两个方程的情况：
$$
\begin{cases}
x\equiv a _ 1 \pmod { m _ 1 }
\\
x \equiv a _ 2 \pmod { m _ 2 }
\end{cases}
$$求解方程 $ m _ 1 p - m _ 2 q = a _ 2 - a _ 1 $，则最后方程组的解是：
$$x \equiv m _ 1 p + a _ 1 \pmod { \operatorname{lcm} ( m _1 ,m _2 ) }$$
威尔逊定理：
$$\forall p \in \mathcal{P} , ( p - 1 ) ! \equiv -1 \pmod { p }$$
规定 $( n ! ) _ p = n ! / ( \lfloor n / p \rfloor ! p ^ { \lfloor n / p \rfloor})$。
推论：$\forall p \in \mathcal { P }, q \in { \mathbb{ N } _ +} , ( p ^ q ! ) _ p \equiv \pm 1 \pmod { p ^ q }$，当且仅当 $p = 2$ 且 $q \ge 3$ 时取正。
推论：$\forall p \in \mathcal {P}, q \in \mathbb{ N } _ + , N _ 0 = n \bmod p ^ q, ( n ! ) _ p \equiv ( \pm 1 ) ^ { \lfloor n / p ^ q \rfloor} ( N _ 0 ! ) _ p \pmod {p ^ q}$。
升幂定理：
记 $v _ p ( n ) $ 为素数 $p$ 在 $n$ 中出现的次数，即 $p ^ { v _ p (n)}$ 恰好整除 $p$，而 $ p ^ { v _ p ( n ) + 1}$ 不行。
对于模为奇素数：$n \in \mathbb { N } _ +$，$p \nmid a , b$，$a \equiv b \pmod {p }$，有：
$$ v _ p ( a ^ n - b ^ n ) = v _ p ( a - b ) + v _ p ( n )$$
对于模为二：$n \in \mathbb{ N } _ + $，$a , b$ 都是奇数，有：
若 $n$ 为奇数：
$$v _ 2 ( a ^ n - b ^ n ) = v _ 2 ( a - b ) $$
若 $n$ 为偶数：
$$v _ 2 ( a ^ n - b ^ n ) = v _ 2 ( a - b ) + v _ 2 ( a + b ) + v _ 2 ( n ) - 1 $$
卢卡斯定理：
对于所有 $p \in \mathcal{P}$，有：
$$\binom { n } { m } \equiv \binom {\lfloor n / p \rfloor} {\lfloor m / p \rfloor} \binom {n \bmod p} {m \bmod p} \pmod{p}$$
拉格朗日定理：
设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式
$$\begin{matrix} f ( x ) = a _ n x ^ { n } + \cdots + a _ 0 & (p \nmid a _ n) \end{matrix}$$
的同余方程 $f ( x ) \equiv 0 \pmod {p}$ 在模 $p$ 意义下至多有 $n$ 个不同解。
阶：
称满足同余式 $a ^ n \equiv 1 \pmod {m}$ 的最小正整数 $n$ 为 $a$ 模 $m$ 的阶，记作 $\delta _ m (a )$。
性质 1：$a , a ^ 2, \cdots , a ^ { \delta _ m ( a )}$ 模 $m$ 两两不同余。
性质 2：若 $a ^ n \equiv 1 \pmod {m}$，则 $ \delta _ m ( a ) \mid n$。
性质 3：若 $a ^ p \equiv a ^ q \pmod {m}$，则 $p \equiv q \pmod {\delta _ m ( a )}$。
性质 4：若 $m \in \mathbb{ N } _ +$，$ a , b \in \mathbb{Z}$，$\gcd (a ,m ) = \gcd ( b ,m ) = 1$，则：
$$\delta _ m ( a b ) = \delta _ m ( a ) \delta _ m ( b ) \Leftrightarrow \gcd (\delta _ m ( a ) , \delta _ m ( b )) = 1$$
性质 5：设 $k \in \mathbb{ N }$，$ m \in \mathbb{ N } _ +$，$a \in \mathbb{ Z }$，$\gcd( a , m ) = 1$，则：
$$\delta _ m ( a ^ k ) = \dfrac {\delta _ m ( a )} { \gcd ( \delta _ m ( a ), k)}$$
原根：
设 $m \in \mathbb{ N } _ + $，$a \in \mathbb{ Z }$，若 $\gcd ( a , m ) = 1$，且 $\delta _ m ( a ) = \varphi ( m )$，则称 $a$ 为模 $m$ 的原根。
原根判定定理：设 $m \ge 3$，$\gcd ( a , m ) = 1$，则 $a$ 是模 $m$ 的原根的充要条件是，对于 $\varphi ( m )$ 的每个素因数 $p$，都有 $a ^ { \varphi ( m ) / p} \not\equiv 1 \pmod {m}$。
若一个数有原根，则它的原根个数为 $\varphi ( \varphi ( m ) )$。
原根存在定理：$m$ 存在原根当且仅当 $m = 2 , 4 , p ^ { \alpha } , 2 p ^ { \alpha }$，其中 $p$ 为奇素数，$\alpha \in \mathbb{ N } _ +$。
若 $m$ 有原根，则其最小原根是不多于 $m ^ { 1 / 4 }$ 级别的。
杂项
《具 体 数 学》
有 手 就 行：
求导链式法则：
$$\begin{aligned}
\dfrac{\delta}{\delta x}f(g(x))=\dfrac{\delta g(x)}{\delta x}\dfrac{\delta}{\delta g(x)}f(g(x))
\end{aligned}$$积分链式法则：
$$\int f’(g(x))g’(x)\delta x=f(g(x))+C$$
分部积分：
$$\int f’(x)g(x)\delta x+\int f(x)g’(x)\delta x=f(x)g(x)$$
洛必达：
$$\lim_{x\to a}\dfrac{f(x)}{g(x)}=\lim_{x\to a}\dfrac{f’(x)}{g’(x)}$$
泰勒展开与麦克劳林级数：
$$
f(x)=\sum_{i=0}^{\infty}\dfrac{f^{(i)}(a)}{i!}(x-a)^i
$$
关于这个：
$$\begin{aligned}
\sum_{i=1}^{n}i^2 &= \dfrac{n(n+1)(2n+1)}{6}
\\ &= \binom{n+2}{3}+\binom{n+1}{3}
\\
&= \dfrac{1}{4}\binom{2n+2}{3}
\\
&= n\binom{n+1}{2}-\binom{n+1}{3}
\end{aligned}$$证明：
法一：归纳法。略（你都记住这个结论了还归纳证个球啊）。
法二：利用一个 $(n+1)^3=n^3+3n^2+3n+1$。
考虑作差，就能得到：
$$\begin{aligned}
\sum_{i=1}^{n}[(i+1)^3-i^3]
& = (n+1)^3-1
\\
&= n^3+3n^2+3n
\end{aligned}$$而我们又知道：
$$\begin{aligned}
\sum_{i=1}^{n}[(i+1)^3-i^3]
&= \sum_{i=1}^{n} (3i^2+3i+1)
\\
&= 3\sum_{i=1}^{n}i^2+3\sum_{i=1}^{n}i+n
\\
&= 3\sum_{i=1}^{n}i^2+\dfrac{3n(n+1)}{2}+n
\end{aligned}$$我们设 $S=\sum_{i=1}^ni^2$，联立上面两个等式：
$$3S+\dfrac{3n(n+1)}{2}+n=n^3+3n^2+3n$$
解一下就是：
$$S=\dfrac{n^3}{3}+\dfrac{n^2}{2}+\dfrac{n}{6}$$
这个式子和那个因式分解的式子是等价的。想要得到那个饮食分解的式子并不需要什么技巧，只需要你会简单的十字相乘就可以了。
我只是单纯地把组合数的式子从百度上抄了下来，然而我并不想去证这个东西。。。
这个式子实际上是冯哈伯公式的特殊情况，和伯努利数有一点关系，这里就略了。。。
主定理：懒了。
求约数个数（听起来就很 sb）：
$$Ans=\prod_{i=1}^{m}(c_i+1)$$
直线分割：
裂项事实：
循环小数相关：
秦九韶公式：
$$a_nx^n+a_{n-1}x^{n-1}+\cdots + a_1x+a_0$$
对于这种多项式，我们的计算复杂度是 $O(n^2)$ 的。运用秦九韶公式，可以优化到 $O(n)$。
我忘了秦九韶公式的严谨定义了，不过看一个式子就能理解怎么做了：
$$\begin{aligned}
& 7x^4+3x^3+9x^2+3x+9
\\
=& x(x(x(7x+3)+9)+3)+9
\end{aligned}$$