简单的好玩的 数学题
题单介绍
# 转自 [HohleFeuerwerke](https://www.luogu.com.cn/user/143271#main) 的原创题单
[原版地址](https://www.luogu.com.cn/paste/pjzw8rsm)https://www.luogu.com.cn/paste/pjzw8rsm
## 题单简述
都是一些好玩的数学题昂。~~由于Karry神仙不让我整理多项式的题并且我的多项式学的也不好，所以这一个题单里面几乎没有多项式的题目。不毒瘤，请放心食用。~~
什么难度的都有，并且几乎所有人都能找到所需。
蓝色题目及以上会用`*`标记。请注意区分以达到更好的训练效果。
### Prat 1 关于素数
如果你对这一块内容不太熟悉，可以先阅读[我的这篇文章](https://www.luogu.com.cn/blog/ilove-zly666/ge-zhong-su-shuo-shai-fa-xue-xi-bi-ji)。
#### 1.1 判断素数
最基本的判断素数莫过于著名的 $\Theta(\sqrt{n})$ 的素数判断板子：
```cpp
bool isprime(int n){
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)return false;
return true;
}
```
[NOIp2002普及组 P1036-选数](https://www.luogu.com.cn/problem/P1036)：这个题直接爆搜，然后每个结果判断一下是不是素数。
[NOIp2008提高组 P1125-笨小猴](https://www.luogu.com.cn/problem/P1125)：这个题直接暴力遍历，然后统计出现次数最多的和出现次数最少的就行了。
[NOIp2012普及组 P1075-质因数分解](https://www.luogu.com.cn/problem/P1075)：这个题他只是冠了一个素数的名字，其实跟素数没什么太大关系。实在要扯上一点关系的话就是每个数都去判断一下是不是素数吧。
[P1218-[USACO1.5]特殊的质数肋骨 Superprime Rib](https://www.luogu.com.cn/problem/P1218)：这个简单题啊，直接暴力。因为 $n\leq 8$ 所以我们可以直接判断一个八位数是不是素数，也不超时啊。dfs 即可。
[P1304-哥德巴赫猜想](https://www.luogu.com.cn/problem/P1304)：大水题，直接上手暴力判断素数然后枚举即可。
[P1579-哥德巴赫猜想（升级版）](https://www.luogu.com.cn/problem/P1579)：大水题，素数判断即可。需要注意的是只需要循环两个数，剩下那个可以 $\Theta(1)$ 无脑减法求出。
[*P4718-【模板】Pollard-Rho算法](https://www.luogu.com.cn/problem/P4718)：这题是分解素因数的快速算法 pollard-rho 的模板题，用到了复杂度很低的判断素数的算法 Miller-Rabin，可以详细地学习一下。
#### 1.2 素数筛法
[P3383-【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)：素数筛法模板题。
[P1835-素数密度](https://www.luogu.com.cn/problem/P1835)：先打表，然后大范围时埃氏筛（根据小范围的素数表）即可。
[* P6052 [RC-02] yltx 数对](https://www.luogu.com.cn/problem/P6052)：这个题原来可以打表过，由于毒瘤yltx的暴行，我们需要用bitset优化埃氏筛。线性筛会爆空间，所以不能通过。
### Prat 2 关于 GCD（最大公约数）
这是[GCD 的 OI-Wiki](https://oi-wiki.org/math/gcd/)，如果对这一块内容不太熟悉，同样建议先阅读。
#### 2.1 关于GCD的基本概念
[P6068-[MdOI2020] GCD? GCD!](https://www.luogu.com.cn/problem/P6068)：这个题非常适合上手学习 gcd。尤其是部分分，我个人非常建议把每一个部分分都写一遍，以加深对gcd的理解。
[P1888-三角函数](https://www.luogu.com.cn/problem/P1888)：大水题，需要注意的是处理最简分数，需要维护两个数的 gcd 以达到约分的效果。
[NOIp2014普及组 P2118-比例简化](https://www.luogu.com.cn/problem/P2118)：这个题裸眼观察可得就是让我们求 gcd，然后约分。
[*山东省选2009 P2152-[SDOI2009]SuperGCD](https://www.luogu.com.cn/problem/P2152)：这个题也很水。注意到我们用辗转相除发求高精度 GCD 需要用到高精度除法和乘法和取模，复杂度很高，给出一种类二进制递归求高精度 GCD 的算法。思想就是：当 $x,y$ 都是偶数时，$\gcd(x,y)=2*\gcd(\frac{x}{2},\frac{y}{2})$。当 $x,y$ 都是奇数时，$\gcd(x,y)=\gcd(x-y,y)$。当 $x$ 为奇数 $y$ 为偶数时， $\gcd(x,y)=\gcd(x,\frac{y}{2})$。同样的，如果 $x$ 为偶数而 $y$ 为奇数，则将 $x$ 除以二。
#### 2.2 需要推式子的GCD
[NOIp2001普及组 P1029-最大公约数和最小公倍数问题](https://www.luogu.com.cn/problem/P1029)：这个题考察的是 $\text{lcm}(a,b)\cdot \gcd(a,b)=a\cdot b$ 这个基本的式子。
[*NOIp2009提高组 P1072-Hankson 的趣味题](https://www.luogu.com.cn/problem/P1072)：这个题真的不难嗷，就是稍微推一下式子然后暴力就是了。
[*山东省选2008 P2158-[SDOI2008]仪仗队](https://www.luogu.com.cn/problem/P2158)：这个题也不是很难，稍微跟着题解推一下式子就行了。显然，当横纵坐标的 GCD >1 的时候就会被遮挡，根据这个性质去推一推式子就行了。
[*山东省选2015 P3327-[SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327)：推式子题，推完以后预处理一下就可以愉快的 $\Theta(1)$ 访问了。
[P1372 又是毕业季I](https://www.luogu.com.cn/problem/P1372)：简单题，倍数时结果最大。
### Part 3 关于逆元
如果你对这块内容不是很熟悉，建议先去阅读[这篇文章](https://www.cnblogs.com/zwfymqz/p/7730375.html)。
#### 3.1 求出逆元的值
[P3811-【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811)：可以使用上述文章中的三种解法之一进行求解。同样的在上述文章中还有 [loj的逆元模板题](https://loj.ac/problem/110)。
[P5431-【模板】乘法逆元2](https://www.luogu.com.cn/problem/P5431)：毒瘤鱼神出的黑科技题。但是好像并不是很难的亚子，我们只需要把 $n$ 个分数相加即可。稍微卡卡常数啊。可以看一看mrsrz的题解。
#### 3.2 应用逆元方法求解的题目
[P1226-【模板】快速幂||取余运算](https://www.luogu.com.cn/problem/P1226)：快速幂板子题。
[湖南省选2008 P3197-[HNOI2008]越狱](https://www.luogu.com.cn/problem/P3197)：这题用快速幂处理一下逆元就做完了。
### Part 4 关于神仙筛法
建议学习 Min_25，洲阁，杜教筛等神仙筛法以后再来这里玩耍啊。
推荐前置阅读[杜教筛学习教程](https://www.cnblogs.com/zwfymqz/p/9341696.html)。
#### 4.1 筛法模板
[*P4213-【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213)：杜教筛模板。
[*P5325-【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)：Min_25筛模板。
#### 4.2 引用筛法的题目
[*P6055-[RC-02] GCD](https://www.luogu.com.cn/problem/P6055)：杜教筛题，几乎就是一个板子题。
[*P3768-简单的数学题](https://www.luogu.com.cn/problem/P3768)：杜教筛题，这个题要推式子，然后再套杜教筛板子就好了。
[*P5282-【模板】快速阶乘算法](https://www.luogu.com.cn/problem/P5282)：Attention: 这个题应用了 Min_25 筛，但是还需要用到其它多项式算法。
### Part 5 高精度
贴个板子，然后基本上完事了。
所以重要的还是把板子背出来（（（
#### 5.1 需要高精度的非数学题
不列举了，有一个很著名的题目：
[*CSP2019-S P5665-划分](https://www.luogu.com.cn/problem/P5665)：毛啸题，所以很毒瘤。当然可以用`__int128`水过，但是这样对你毫无帮助。
#### 5.2 需要高精度的数学题
[NOIp1998普及组 P1009-阶乘之和](https://www.luogu.com.cn/problem/P1009)：这个题直接推，高精即可。
[P1601-A+B Problem（高精）](https://www.luogu.com.cn/problem/P1601)：高精度板子题。
[P1760-通天之汉诺塔](https://www.luogu.com.cn/problem/P1760)：式子显然的题，因为大家都推过这个式子。这个题直接高精度就好了。
[*湖南省选2004 P2293-[HNOI2004]高精度开根](https://www.luogu.com.cn/problem/P2293)：这个题更加的水，因为只有一个高精度和一个二分。
[NOIp2003普及组 P1045-麦森数](https://www.luogu.com.cn/problem/P1045)：高精简单题。
### Part 6 其他
#### 6.1 秦九韶算法
[*NOIp2014提高组 P2312-解方程](https://www.luogu.com.cn/problem/P2312)：这个题需要了解的是秦九韶算法，然后就直接做完了。
#### 6.2 高斯消元
[*P3389-【模板】高斯消元](https://www.luogu.com.cn/problem/P3389)：高斯消元模板题。高斯消元的思想就是通过矩阵变换求出一个方程的解。
[*P2455-[SDOI2006]线性方程组](https://www.luogu.com.cn/problem/P2455)：高斯消元模板题，第二个，并且这两题都需要用double。
#### 6.3 杂题
[NOIp2001提高组 P1024-一元三次方程求解](https://www.luogu.com.cn/problem/P1024)：二分题，暴力题，甚至可以用盛金公式来做。
[CF1321A-Contest for Robots](https://www.luogu.com.cn/problem/CF1321A)：数学题，逻辑推理题，但是不难。
[*P1286-两数之和](https://www.luogu.com.cn/problem/P1286)：推式子爆搜的题。
[*重庆省选2009 P1627-[CQOI2009]中位数](https://www.luogu.com.cn/problem/P1627)：排序题。维护一个map统计即可。代码很短。
[*P5084 轮换式](https://www.luogu.com.cn/problem/P5084)：被Fee_cle6418称为SBT的题。主要是这题能够加强。考虑一种推式子然后递推的方法就能过了。
[*P4619 旧试题](https://www.luogu.com.cn/problem/P4619)：简单反演，神仙优化题。