前置知识：
基本概念：
带余除法：
给定一个整数 $a$ 和一个正整数 $q$，总能找到一个整数 $b$ 使得 $a=bq+r(0\leq r<q)$。我们称 $r$ 为 $a$ 被 $q$ 除的余数。
模运算：
对于一个带余除法：$a=bq+r$，可表述为 $a\bmod q=r$。
同余：
若 $a=b_1q+r,A=b_2q+r$，则称 $a,A$ 同余，写作 $a\equiv A\pmod q$。
整除：
若 $a=bq+r,r=0$ 即 $a=bq$，则称 $q$ 整除 $a$。
约数和倍数：
如果一个整数 $a$ 能被正整数 $b$ 整除，则称 $a$ 是 $b$ 的倍数，$b$ 是 $a$ 的约数。
tips:
- 约数和倍数是定义在整数域上的概念。
- 正整数 $a$ 的两个倍数的和差还是 $a$ 的倍数。
- 约数一定是正整数，倍数可以是负整数或零。（负整数的约数等价于它的相反数的约数）
- $0$ 的约数为全体正整数，$0$ 没有倍数的定义。
最大公约数和最小公倍数：
如果正整数 $p$ 同时是两个整数 $a,b$ 的约数，我们就称 $p$ 为 $a,b$ 的公约数。$a,b$ 的所有公约数中最大的那个数被称为 $a,b$ 的最大公约数。
如果正整数 $p$ 同时是两个整数 $a,b$ 的倍数，我们就称 $p$ 为 $a,b$ 的公倍数。$a,b$ 的所有公倍数中最小的那个数被称为 $a,b$ 的最小公倍数。
tips:
- $0,0$ 不存在最大公约数。
- 任何整数和 $0$ 的最大公约数都是它本身。
质数：
对于一个正整数 $a$，如果 $a$ 只有 $1$ 和 $a$ 两个约数，就称它为质数。
两个整数的最大公约数如果为 $1$，就称这两个数是互质的。
常见符号：
- 整除符号：$x\mid y$，表示 $x$ 整除 $y$。
- 取模符号：$x\bmod y$，表示 $x$ 除以 $y$ 得到的余数。
- 互质符号：$x\perp y$，表示 $x,y$ 互质。
- 最大公约数：$\gcd(x,y)$，在无混淆意义的时候可以写作 $(x,y)$。
- 最小公倍数：$\text{lcm}(x,y)$，在无混淆意义的时候可以写作 $[x,y]$。
- 阶乘：$x!=1\times2\times3\times…\times x$。
- 向下取整：$\lfloor x\rfloor$，表示小于等于 $x$ 的最小整数。
- 向上取整：$\lceil x\rceil$，表示大于等于 $x$ 的最小整数。
- 组合数：$\binom{x}{y}$，即：$C_x^y$。