Part 6.1-6.4 数学

# Part 6 数学 > OI 中的数学知识很多，也有些杂乱。 ## Part 6.1 位运算 > 将十进制整数转换为二进制后，有很多按位运算的运算符。 > > 如果能善于利用位运算的一些性质，往往能达到事半功倍的效果。 - [P5657 格雷码](https://www.luogu.com.cn/problem/P5657) - [P5514 [MtOI2019]永夜的报应](https://www.luogu.com.cn/problem/P5514) - [P5538 【XR-3】Namid[A]me](https://www.luogu.com.cn/problem/P5538) - [P5539 【XR-3】Unknown Mother-Goose](https://www.luogu.com.cn/problem/P5539) - [P5523 [yLOI2019]珍珠](https://www.luogu.com.cn/problem/P5523) ## Part 6.2 整除相关 > 与整除相关的概念有很多，比较常用的有素数，最大公约数和欧拉函数。 ### Part 6.2.1 素数 > 素数，指的是除 1 和它本身之外没有其他约数的数。 - [P4718 【模板】Pollard-Rho算法](https://www.luogu.com.cn/problem/P4718) - [P1075 质因数分解](https://www.luogu.com.cn/problem/P1075) - [P2441 角色属性树](https://www.luogu.com.cn/problem/P2441) - [P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535) ### Part 6.2.2 最大公约数 > 如果两个数有一个共同的约数，那么这个约数就被称为公约数。最大公约数就是指这两个数的所有公约数中，最大的一个。 > > 求解两个数的最大公约数，可以采用欧几里得算法解决。 - [P5435 【模板】快速 GCD](https://www.luogu.com.cn/problem/P5435) - [P5436 【XR-2】缘分](https://www.luogu.com.cn/problem/P5436) - [P1029 最大公约数和最小公倍数问题](https://www.luogu.com.cn/problem/P1029) - [P1414 又是毕业季II](https://www.luogu.com.cn/problem/P1414) - [P2152 [SDOI2009]SuperGCD](https://www.luogu.com.cn/problem/P2152) - [P1072 Hankson 的趣味题](https://www.luogu.com.cn/problem/P1072) ### Part 6.2.3 欧拉函数 > 欧拉函数 $ \varphi (x) $ 表示了小于 $ x $ 的数字中，与 $ x $ 互质的数字个数。 - [P2158 [SDOI2008]仪仗队](https://www.luogu.com.cn/problem/P2158) - [P2568 GCD](https://www.luogu.com.cn/problem/P2568) - [P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398) - [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139) ## Part 6.3 同余方程 > 求解同余方程往往可以引出不少话题。 ### Part 6.3.1 线性同余方程&乘法逆元 > 线性同余方程是同余方程中最基础的内容。 - [P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549) - [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613) - [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811) - [P5431 【模板】乘法逆元2](https://www.luogu.com.cn/problem/P5431) - [P1082 同余方程](https://www.luogu.com.cn/problem/P1082) - [P3951 小凯的疑惑](https://www.luogu.com.cn/problem/P3951) - [P1516 青蛙的约会](https://www.luogu.com.cn/problem/P1516) ### Part 6.3.2 中国剩余定理 > 中国剩余定理可以快速解一元线性同余方程组。 - [P4777 【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.com.cn/problem/P4777) - [P3868 [TJOI2009]猜数字](https://www.luogu.com.cn/problem/P3868) - [P2480 [SDOI2010]古代猪文](https://www.luogu.com.cn/problem/P2480) - [P4774 [NOI2018]屠龙勇士](https://www.luogu.com.cn/problem/P4774) - [P5345 【XR-1】快乐肥宅](https://www.luogu.com.cn/problem/P5345) ### Part 6.3.3 高次同余方程 > BSGS 算法可以高效计算离散对数。 > > 而高次剩余的求解更加复杂，其中二次剩余作为高次剩余中比较特殊的情况，可以使用 Cipolla 法求解。 - [P4195 【模板】exBSGS](https://www.luogu.com.cn/problem/P4195) - [P5491 【模板】二次剩余](https://www.luogu.com.cn/problem/P5491) - [P3306 [SDOI2013]随机数生成器](https://www.luogu.com.cn/problem/P3306) - [P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485) ## Part 6.4 博弈论 > 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。 - [P2197 【模板】nim游戏](https://www.luogu.com.cn/problem/P2197) - [P1288 取数游戏II](https://www.luogu.com.cn/problem/P1288) - [P1290 欧几里德的游戏](https://www.luogu.com.cn/problem/P1290) - [P1247 取火柴游戏](https://www.luogu.com.cn/problem/P1247) - [P2252 取石子游戏](https://www.luogu.com.cn/problem/P2252)