【NOIP 6】数论
题单介绍
## 数论
`- [x]` 表示基础任务，`- [ ]` 表示目前阶段可选择性了解
- [x] 找规律！找规律！！一定要找规律！！！这很重要，看到题一定要先试试能不能找规律，不然，万一你推式子水平不够到位，还碰上了 [NOIP 2018 D2T2](https://www.luogu.com.cn/problem/P5023)，或是 [NOI 2019 D2T2](https://www.luogu.com.cn/problem/P5472)，你就会像我一样，爱上这款████的游戏
- [x] 数论
- [x] 整除性
- [x] 定义：整除、带余除法、gcd
- [x] 裴蜀定理、欧几里得算法
- [x] 扩展欧几里得算法 [https://oi-wiki.org/math/gcd/](https://oi-wiki.org/math/gcd/)
- [x] 方程：$ax + by = c$
- [x] 素数
- [x] 定义：素数
- [x] 算术基本定理
- [x] 埃氏筛法、欧拉筛法、求任意积性函数 1~n 处的值 [https://oi-wiki.org/math/sieve/](https://oi-wiki.org/math/sieve/)
- [x] 同余
- [x] 线性同余方程组
- [x] 线性同余方程 $bx\equiv a\pmod n$ [https://oi-wiki.org/math/linear-equation/](https://oi-wiki.org/math/linear-equation/)
- [x] 合并两个形如 $x\equiv a\pmod n$ 的方程 [链接同下，不知为何被人称为“exCRT”](https://oi-wiki.org/math/crt/)
- [x] 中国剩余定理、直接构造解 [https://oi-wiki.org/math/crt/](https://oi-wiki.org/math/crt/)
- [x] 将 $\bmod n$ 的问题分解为 $\bmod p^k$ 的问题，然后合并
- [x] Lucas定理 [https://oi-wiki.org/math/lucas/](https://oi-wiki.org/math/lucas/)
- 基础：
* P1075 [NOIP2012 普及组] 质因数分解
- 快速幂：
* P1226 【模板】快速幂||取余运算
* P1965 [NOIP2013 提高组] 转圈游戏
* P3197 [HNOI2008]越狱
- 逆元：
* P3811 【模板】乘法逆元
* P5431 【模板】乘法逆元 2
* P2613 【模板】有理数取余
* P1082 [NOIP2012 提高组] 同余方程
- 扩展欧几里得算法：
* P5656 【模板】二元一次不定方程 (exgcd)
* P4549 【模板】裴蜀定理
* P1516 青蛙的约会
* P2421 [NOI2002] 荒岛野人
- 费马小定理和欧拉定理及其扩展：
* P5091 【模板】扩展欧拉定理
* U55950 【模板】扩展欧拉定理
* P2155 [SDOI2008] 沙拉公主的困惑
* P4139 上帝与集合的正确用法
* CF906D Power Tower
* SP10050 POWTOW - Power Tower City
* P3934 [Ynoi2016] 炸脖龙 I
* P3747 [六省联考 2017] 相逢是问候
- 扩展中国剩余定理：
* P1495 【模板】中国剩余定理(CRT)/曹冲养猪
* P3868 [TJOI2009] 猜数字
* P4774 [NOI2018] 屠龙勇士
- Lucas 定理：
* P3807 【模板】卢卡斯定理/Lucas 定理
* P2480 [SDOI2010]古代猪文
- 一般的组合数取模（扩展 Lucas 定理）：
* P4720 【模板】扩展卢卡斯定理/exLucas
* P2183 [国家集训队]礼物
* P3301 [SDOI2013]方程
* P3726 [AH2017/HNOI2017]抛硬币
- 基础筛法：
* P3383 【模板】线性筛素数
* P3912 素数个数
* P1835 素数密度
* P1865 A % B Problem
* [LibreOJ #124. 除数函数求和 1](https://loj.ac/p/124)
* P2568 GCD
* P2303 [SDOI2012] Longge 的问题
* P2158 [SDOI2008] 仪仗队
* P2398 GCD SUM
* P1390 公约数的和
* P1447 [NOI2010] 能量采集（莫比乌斯反演）
- 矩阵快速幂：
* P3390 【模板】矩阵快速幂
* P1939 【模板】矩阵加速（数列）
* P1349 广义斐波那契数列
* P2044 [NOI2012] 随机数生成器