一些有趣的数论题 Part 1

Link：[Part 2](https://www.luogu.com.cn/training/87630)。 ------------ 本题单中的题目均与**数论**相关。其中有模板题，也有人类智慧题；有小清新结论题，也有重工业题。希望本题单能对大家有所帮助。 题目按难度、题库和题号排序。欢迎私信添加题目。 ------------ 1. gcd & lcm - [P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题](https://www.luogu.com.cn/problem/P1029)：利用 gcd 和 lcm 的性质枚举。 - [P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)：利用 gcd 的性质求不定方程的一组特解。 - [P2158 [SDOI2008] 仪仗队](https://www.luogu.com.cn/problem/P2158)：容斥 / 欧拉函数 / 莫比乌斯反演。 - [P6210 「SWTR-04」Easy Math Problems](https://www.luogu.com.cn/problem/P6210)：容斥 + 筛 gcd / 莫比乌斯反演 + 二分答案。 - [CF1656H Equal LCM Subsets](https://www.luogu.com.cn/problem/CF1656H)：稍微有点人类智慧的转化 + 线段树维护 gcd。 2. 质数、积性函数 & 筛法 - *[P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383) - [P1865 A % B Problem](https://www.luogu.com.cn/problem/P1865)：线性筛 + 前缀和。 - [P1835 素数密度](https://www.luogu.com.cn/problem/P1835)：区间筛。 - [P1463 [POI2002 / HAOI2007] 反素数](https://www.luogu.com.cn/problem/P1463)：搜索 + 利用反素数的性质剪枝。 - [P2261 [CQOI2007] 余数求和](https://www.luogu.com.cn/problem/P2261)：数论分块。 - [P4626 一道水题 II](https://www.luogu.com.cn/problem/P4626)：线性筛 + 构造。 - [P6810 「MCOI-02」Convex Hull 凸包](https://www.luogu.com.cn/problem/P6810)：根据 $\tau$ 的定义推式子。 - [P5495 狄利克雷前缀和](https://www.luogu.com.cn/problem/P5495)：狄利克雷前缀和。 - *[P4213 【模板】杜教筛](https://www.luogu.com.cn/problem/P4213) - [P5493 质数前缀统计](https://www.luogu.com.cn/problem/P5493)：Min_25 筛前半部分。 - [P7580 「RdOI R2」因数和](https://www.luogu.com.cn/problem/P7580)：狄利克雷前缀和 + 卡常 / 快速狄利克雷卷积。 - *[P7884 【模板】Meissel–Lehmer 算法](https://www.luogu.com.cn/problem/P7884) - [SP288 PON - Prime or Not](https://www.luogu.com.cn/problem/SP288)：Miller-Rabin。 - [SP6488 PRIMES2 - Printing some primes (Hard)](https://www.luogu.com.cn/problem/SP6488)：Wheel Factorization。 - *[P5325 【模板】Min_25 筛](https://www.luogu.com.cn/problem/P5325) - [P8104 「LCOI2021」Cow Function](https://www.luogu.com.cn/problem/P8104)：Min_25 筛（+ 单位根反演）。 - [SP6489 KPRIMES2 - Finding the Kth Prime (Hard)](https://www.luogu.com.cn/problem/SP6489)：SP6488 加强版。 - [SP34112 UDIVSUM - The Sum of Unitary Divisors](https://www.luogu.com.cn/problem/SP34112)：Powerful Number 筛 / 莫比乌斯反演。 3. 费马小定理、欧拉函数和（扩展）欧拉定理 - [P1390 公约数的和](https://www.luogu.com.cn/problem/P1390)：欧拉反演 / 莫比乌斯反演。 - [P2155 [SDOI2008] 沙拉公主的困惑](https://www.luogu.com.cn/problem/P2155)：欧拉函数。 - [P2568 GCD](https://www.luogu.com.cn/problem/P2568)：欧拉函数 / 莫比乌斯反演。 - *[P5091 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091) - [P3747 [六省联考 2017] 相逢是问候](https://www.luogu.com.cn/problem/P3747)：预处理幂塔（光速幂 / 利用结论）+ 线段树 / 树状数组 + 并查集。 - [CF906D Power Tower](https://www.luogu.com.cn/problem/CF906D) / [SP10050 POWTOW - Power Tower City](https://www.luogu.com.cn/problem/SP10050)：幂塔取模。 5. exgcd、逆元和 ((ex)ex)CRT - *[P3811 【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811) - [P4071 [SDOI2016] 排列计数](https://www.luogu.com.cn/problem/P4071)：递推 + 阶乘逆元。 - *[P5656 【模板】二元一次不定方程 (exgcd)](https://www.luogu.com.cn/problem/P5656) - *[P1495 【模板】中国剩余定理 (CRT) / 曹冲养猪](https://www.luogu.com.cn/problem/P1495) - [P2054 [AHOI2005] 洗牌](https://www.luogu.com.cn/problem/P2054)：推式子 + exgcd 求逆元。 - [P4774 [NOI2018] 屠龙勇士](https://www.luogu.com.cn/problem/P4774)：multiset / 平衡树 + exexCRT。 - *[P4777 【模板】扩展中国剩余定理 / exCRT](https://www.luogu.com.cn/problem/P4777) 6. 阶、原根、离散对数和 N 次剩余 - *[P3846 【模板】BSGS / [TJOI2007] 可爱的质数](https://www.luogu.com.cn/problem/P3846) - [P2485 [SDOI2011] 计算器](https://www.luogu.com.cn/problem/P2485)：快速幂 + exgcd + BSGS。 - *[P6091 【模板】原根](https://www.luogu.com.cn/problem/P6091) - [P3306 [SDOI2013] 随机数生成器](https://www.luogu.com.cn/problem/P3306)：推式子 + 逆元 + BSGS。 - *[P4195 【模板】exBSGS](https://www.luogu.com.cn/problem/P4195) - [P5110 块速递推](https://www.luogu.com.cn/problem/P5110)：待定系数法 / 生成函数 + 光速幂。 - *[P5491 【模板】模奇质数的二次剩余](https://www.luogu.com.cn/problem/P5491) - [P6736 「Wdsr-2」白泽教育](https://www.luogu.com.cn/problem/P6736)：BSGS + 模意义下的幂塔方程。 - [P5605 小 A 与两位神仙](https://www.luogu.com.cn/problem/P5605)：阶 + Pollard-Rho。 - *[P5668 【模板】N 次剩余](https://www.luogu.com.cn/problem/P5668) - [P6610 [Code+#7] 同余方程](https://www.luogu.com.cn/problem/P6610)：二次剩余神题。 - [[ABC335G] Discrete Logarithm Problems](https://www.luogu.com.cn/problem/AT_abc335_g)：阶。 - [LOJ6542 离散对数](https://loj.ac/p/6542)：Index Calculus 算法。 7. (ex)Lucas - *[P3807 【模板】卢卡斯定理](https://www.luogu.com.cn/problem/P3807)