NOI 2023 一轮复习Ⅰ：数论
阅读须知：
本系列博客主要为个人复习所用，可供各位参考。
整理的知识点不会涉及较为偏僻的知识点，以 NOI 考察过的知识点为主。
按照目前的想法，想分成 数论函数、多项式、线性代数、组合计数、字符串、数据结构、图论、网络流、计算几何、构造、非传统题 这些板块进行整理，由于只是最初设想，想必此后会有更新。
知识清单/目录：
- 基本数论
- 欧几里得算法 / 翡蜀定理
- 莫比乌斯反演
- 筛法
1. 基本数论
\(a.\) 顶和底
关于顶和底，我们有 \(\left\lfloor-x\right\rfloor=-\left\lceil x\right\rceil,\left\lceil-x\right\rceil=-\left\lfloor x\right\rfloor,\left\lceil x\right\rceil-\left\lfloor x\right\rfloor=[x\in\mathbb{Z}],\left\lfloor x+n\right\rfloor=\left\lfloor x\right\rfloor+n(n\in\mathbb{Z}),\left\lceil x+n\right\rceil=\left\lceil x\right\rceil+n(n\in\mathbb{Z})\)。
在不等式层面，可以得到 \(x-1<\left\lfloor x\right\rfloor\le x\le\left\lceil x\right\rceil<x+1\)，由此可以得到以下四条放缩法则：
\[\begin{aligned} &\left\lfloor x\right\rfloor=n\Longleftrightarrow n\le x<n+1\\ &\left\lfloor x\right\rfloor=n\Longleftrightarrow x-1<n\le x\\ &\left\lceil x\right\rceil=n\Longleftrightarrow n-1<x\le n\\ &\left\lceil x\right\rceil=n\Longleftrightarrow x\le n<x+1\\ \end{aligned}\]进一步的，我们可以证明，设 \(f(x)\) 且在一个实数区间连续的单调递增函数且满足以下性质
\[f(x)\in\mathbb{Z}\Longrightarrow x\in\mathbb{Z} \]且 \(f(x),f(\left\lfloor x\right\rfloor),f(\left\lceil x\right\rceil)\) 均有定义，则有
\[\begin{aligned}&\left\lfloor f(x)\right\rfloor=\left\lfloor f(\left\lfloor x\right\rfloor)\right\rfloor\\&\left\lceil f(x)\right\rceil=\left\lceil f(\left\lceil x\right\rceil)\right\rceil\\\end{aligned} \]该定理的一个重要特例是
\[\begin{aligned}&\left\lfloor\dfrac{x+m}{n}\right\rfloor=\left\lfloor\dfrac{\left\lfloor x\right\rfloor+m}{n}\right\rfloor\\&\left\lceil\dfrac{x+m}{n}\right\rceil=\left\lceil\dfrac{\left\lceil x\right\rceil+m}{n}\right\rceil\end{aligned} \]我们还可以得到 \(\left\lfloor\dfrac{\left\lfloor\frac{x}{n}\right\rfloor}{m}\right\rfloor=\left\lfloor\dfrac{\left\lfloor\frac{x}{m}\right\rfloor}{n}\right\rfloor=\left\lfloor\dfrac{x}{nm}\right\rfloor\)。
例题 \(1\)