一些有趣的数论题 Part 2

Link：[Part 1](https://www.luogu.com.cn/training/85467)。 ------------ - [P2480 [SDOI2010] 古代猪文](https://www.luogu.com.cn/problem/P2480)：Lucas + 费马小定理 + CRT。 - [P3301 [SDOI2013] 方程](https://www.luogu.com.cn/problem/P3301)：容斥 + exLucas。 - *[P4720 【模板】扩展卢卡斯定理](https://www.luogu.com.cn/problem/P4720) 8. 欧拉反演 & 莫比乌斯反演 - [P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522)：莫比乌斯反演 + 容斥 + 数论分块。 - [P1829 [国家集训队] Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)：莫比乌斯反演。 - [P3327 [SDOI2015] 约数个数和](https://www.luogu.com.cn/problem/P3327)：奇奇怪怪的结论 + 莫比乌斯反演 + 数论分块。 - [P6156 简单题](https://www.luogu.com.cn/problem/P6156) / [P6222 「P6156 简单题」加强版](https://www.luogu.com.cn/problem/P6222)：莫比乌斯反演 + 数论分块。 - [P6271 [湖北省队互测2014] 一个人的数论](https://www.luogu.com.cn/problem/P6271)：莫比乌斯反演 + 自然数幂和。 - [CF645F Cowslip Collections](https://www.luogu.com.cn/problem/CF645F)：倍数形式的莫比乌斯反演。 - [P3704 [SDOI2017] 数字表格](https://www.luogu.com.cn/problem/P3704)：莫比乌斯反演 + 数论分块。 - [P4240 毒瘤之神的考验](https://www.luogu.com.cn/problem/P4240)：莫比乌斯反演 + 数论分块 + 根号分治。 - [P4464 [国家集训队] JZPKIL](https://www.luogu.com.cn/problem/P4464)：莫比乌斯反演 + 伯努利数求自然数幂和。 - [P5518 [MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题](https://www.luogu.com.cn/problem/P5518)：莫比乌斯反演 + 数论分块~~千万别被标题骗了~~。 - [P7890 「MCOI-06」Lost Desire](https://www.luogu.com.cn/problem/P7890)：组合数学 + 数学归纳法 / 打表找规律 + 莫比乌斯反演 + Index Calculus 算法。 9. Pollard-Rho 算法 - *[P4718 【模板】Pollard-Rho 算法](https://www.luogu.com.cn/problem/P4718) - [P4358 [CQOI2016] 密钥破解](https://www.luogu.com.cn/problem/P4358)：Pollard-Rho。 - [P4714 「数学」约数个数和](https://www.luogu.com.cn/problem/P4714)：组合数 + Pollard-Rho。 10. 类欧几里得算法 - *[P5170 【模板】类欧几里得算法](https://www.luogu.com.cn/problem/P5170) - [P5179 Fraction](https://www.luogu.com.cn/problem/P5179)：本质为类欧几里德算法的分类讨论 + 递归。 11. 二项式定理 & 反演 - [P1313 [NOIP2011 提高组] 计算系数](https://www.luogu.com.cn/problem/P1313)：二项式定理。 - [P4859 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859)：dp + 二项式反演。 - [P7360 「JZOI-1」红包](https://www.luogu.com.cn/problem/P7360)：莫比乌斯反演 + Min-Max 反演 + 二项式定理 / 统计质因数的贡献 + 容斥。 - [AT4119 [ARC096C] Everything on It](https://www.luogu.com.cn/problem/AT4119)：二项式反演 / 容斥 + 组合数学 + 欧拉定理。 12. Stern-Brocot 树 - [P8058 [BalkanOI2003] Farey 序列](https://www.luogu.com.cn/problem/P8058)：Stern-Brocot 树上二分 + 莫比乌斯反演 + 类欧几里得算法。 - [[ABC333G] Nearest Fraction](https://www.luogu.com.cn/problem/AT_abc333_g)：Stern-Brocot 树上二分。 - [SP26073 DIVCNT1 - Counting Divisors](https://www.luogu.com.cn/problem/SP26073)：Stern-Brocot 树拟合双曲线 + 单调栈。 13. Kummer 定理 - [CF582D Number of Binominal Coefficients](https://www.luogu.com.cn/problem/CF582D)：Kummer 定理 + 数位 dp。 14. dp 相关的杂题 - [CF1614D1 Divan and Kostomuksha (easy version)](https://www.luogu.com.cn/problem/CF1614D1)：倍数 dp。 - [P7575 「PMOI-3」公约数](https://www.luogu.com.cn/problem/P7575)：dp + 莫比乌斯反演。 - [CF1139D Steps to One](https://www.luogu.com.cn/problem/CF1139D)：因数期望 dp + 莫比乌斯反演。 - [CF1614D2 Divan and Kostomuksha (hard version)](https://www.luogu.com.cn/problem/CF1614D2)：狄利克雷后缀和优化预处理 + 倍数 dp。 - [CF1603D Artistic Partition](https://www.luogu.com.cn/problem/CF1603D)：欧拉函数 + 决策单调性优化 dp。 - [CF1801F Another n-dimensional chocolate bar](https://www.luogu.com.cn/problem/CF1801F)：**上取整**数论分块优化 dp。