qbxt五一数论Day1

目录

I. 基础知识

1. 带余除法(小学)

1. 定义

对于整数 \(a,b\),若有 \(q,r\) 满足:

\[a=bq+r \]

其中 \(0\le r<b\),那么 \(r\) 称作 \(a\) 模 \(b\) 的 余数,记作 \(a\bmod b\) .

顺便一提,\(a=\left\lfloor\dfrac ab\right\rfloor\) .

2. 性质

\[(a+b)\bmod p=((a\bmod p)+(b\bmod p))\bmod p \]

\[(a-b)\bmod p=((a\bmod p)-(b\bmod p))\bmod p \]

\[ab\bmod p=((a\bmod p)(b\bmod p))\bmod p \]

Proof:

设 \(a=a'p+r_0,b=b'p+r_1\),则有:

\[(a+b)\bmod p=(r_0+r_1)\bmod p=((a\bmod p)+(b\bmod p))\bmod p \]

\[(a-b)\bmod p=(r_0-r_1)\bmod p=((a\bmod p)-(b\bmod p))\bmod p \]

\[ab\bmod p=(r_0\cdot r_1)\bmod p=((a\bmod p)(b\bmod p))\bmod p\tag*{□} \]

2. 最大公约数(gcd)/ 最小公倍数(lcm)

II. 矩阵及其应用

1. 定义

\(n\) 行 \(m\) 列的数表就是 矩阵(Martix),矩阵里的数叫做矩阵的 元素(Element),例如下面就是三个矩阵:

\[\begin{bmatrix}1&2\\3&3\end{bmatrix}\quad\begin{Bmatrix}9&3\sqrt 2\\e&0\\-\dfrac 13&\pi^2\end{Bmatrix}\quad,\left(\begin{matrix}3.14&6.28&9.42\\\pi&2\pi&3\pi\end{matrix}\right) \]

矩阵一般用大写字母 \(A,B,C,\cdots\) 表示

特殊的矩阵有:

  • 零矩阵 \(O\),所有元素都是 \(0\) 的矩阵 .
  • 单位矩阵 \(I\)(或写作 \(E\)),对角线是 \(1\),其余为 \(0\) 的矩阵:\(\begin{bmatrix}1&0&0&\cdots&0\\0&1&0&\cdots&0\\0&0&1&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&1\end{bmatrix}\) .
上一篇:同余最短路


下一篇:最大公约数详解