算法模板（5）：数学（1）：数学知识（1）

数论

整数的整除性

1. [x]表示不超过x的最大整数，叫做取整函数或高斯函数。
2. 设整数a，b不同时为零，则存在一对整数m，n，使得$(a,b)=am+bn$。注：a和b的最大公因数会写成 (a, b) 的形式，最小公倍数会写成 [a, b] 的形式。
3. 若$a|bc$，且$(a,b)=1$，则$a|c$。
4. 设p为素数，若 $p|ab$，则 $p|a$，或 $p|b$。推论：设p为素数，若 $p|a_1{a}_2...a_k$，则存在$a_i(1\le i\le k)$，使得$p|a_i$。
5. $(a,b)[a,b]=|ab|$.
6. 求多个整数的最大公因数，可以这样转化：(a, b, c) = ((a, b), c)。求多个整数的最大公倍数，可以转化为：[a, b, c] = [[a, b], c]。
7. 算术基本定理：任何大一1的整数可以分解成素因数乘积的形式，并且，如果不计分解式中素因数的次序，这种分解式是惟一的。
8. 一般地，对给定的两个大于1的整数a, b,找出它们所有的互异素因数，然后将a, b表示成这些素因数的幂的乘积，如果其中一个素因数在a或b中不出现，就将这个素因数的幂指数写作0，那么(a, b)可以表示成这些素因数的幂的乘积，每个素因数的幂指数为其在a与b中的幂指数的最小者，而[a, b]也可以表示成这些素因数幂的乘积，每个素因数的幂指数为其在a与b的幂指数的最大者.

同余

1. $a\equiv b(modn)\iff n|a-b$.
2. 若 $a\equiv b(modn)$，且$c\equiv d(modn)$，则

• $a+c\equiv b+d(modn)$;
• $ac\equiv bd(modn)$
• $ka\equiv kb(modn)$，k为任意整数
• $a^m\equiv b^m(modn)$，m为正整数

3. 若$ab\equiv ac(modn)$，且$(a,n)=1$，则$b\equiv c(modn)$.
4. 我们把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类，记作[a]，并把a叫做剩余类[a]的一个代表元。
5. $a\equiv b(modn)\iff [a]=[b].$
6. 剩余类加法：$[a]+[b]=[a+b]$。剩余类乘法：$[a][b]=[ab]$。
7. [0]叫剩余类环的零元，[1]叫剩余类环的单位元。若$[a]+[b]=[b]+[a]=[0]$，则称[b]为[a]的负元。若$[a][b]=[b][a]=[1]$，则称[b]为[a]的逆元。
8. 非零元[a]有逆元的充要条件是$(a,n)=1$。n就是剩余类定义里面的那个n。
9. 在模n的剩余类环中，若[a]存在逆元，则它的逆元仅有一个。
10. 无零因子：任意两个非零整数的乘积不等于0。但是，剩余类乘法中并不都满足这个条件。比如模6的剩余类乘法，$[2][3]=0$。但是模5的剩余类环无零因子。
11. 设m为素数，a为任意整数，且$(a,m)=1$，则$a^{m-1}\equiv 1(modm)$.
12. 欧拉定理：设 m 为正整数，a 为任意整数，且$(a,m)=1$，则：$a^{\varphi (m)}\equiv 1(modn)$，其中$\varphi (m)$表示1，2，3，…，m 中与m互素的正整数的个数。若在算数基本定理中，$N=p_1^{a_1}\ast p_2^{a_2}\ast \dots \ast p_m^{a_m}$，则：$\phi (N)=N\ast \frac{p_1-1}{p_1}\ast \frac{p_2-1}{p_2}\ast \dots \ast \frac{p_m-1}{p_m}$。不过要指出的是，$\phi (1)=1$。
13. 一次同余方程$ax\equiv b(modn)$有解，则$(a,n)|b$。反过来，当$(a,n)|b$，一次同余方程$ax\equiv b(modn)$恰有(a, n)个解。
14. $\frac{b}{a}\%p=b\ast a^{-1}\%p=b\ast a^{p-2}\%p$

一次不定方程

1. 二元一次不定方程$ax+by=c$有解，等价于$(a,b)|c$。
2. 设$(a,b)=1$，则不定方程ax+by=c的整数通解为$$\{\begin{array}{l}x=x_0+bt\\ y=y_0-at\end{array}$$其中t为任意整数，$x=x_0,y=y_0$为不定方程$ax+by=c$的一个特解。
3. 三元一次不定方程$ax+by+cz=d$有整数解的充要条件是$(a,b,c)|d$

原根与指数

原根

1. 设(a,m) = 1,则
   (i)存在正整数n,$1\le r<m$,使$a^n=1$(mod m);
   (ii)设n为(i)中最小的正整数，则对整数k和l,同余式 $a^k=a^l(modm)$ 成立的充分必要条件是$k\equiv l(modn)$.特别地，$a^k=1(modm)$成立的充分必要条件为n|k.
2. 对与m互素的整数a,满足$a^n=1(modm)$的最小正整数n,称为a模m的阶.

组合数学

组合数

• 一个组合数是否为奇数：$C(n,k)$为奇数时，$n\&k=k$ 。
• 令$a_n={\sum }_{x=0}^N{C}_N^x\ast 2^x$：$a_0=1$，$a_n=3\ast a_{n-1}$。

求和公式

1.平方和公式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SemLiPww-1686468029027)(null)]

2.立方和公式

$\sum _{i=1}^n{i}^3=1^3+2^3+...+n^3=\frac{n^2(n+1{)}^2}{4}=[\frac{n(n+1)}{2}{]}^2$

微积分

积分表

• 积分表1：

• 积分表2：

• 积分表3：

$\pi$ 的值

• 不用记住准确值，一行代码就可以了呀。把这个放在main函数外面也是没问题的。

const double PI = acos(-1);

其他

1. 在数学中，以Kenneth E. Iverson命名的“艾佛森括号”，是一种用方括号记号，如果方括号内的条件满足则为1，不满足则为0。
2. 格雷码规则：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NC5Ypxxs-1686468028452)(file:///D:\1398687709\1398687709\Image\C2C\3144C8683FBA94C26F58702AA73A398E.png)]