第六章
题单介绍
# [返回目录](https://www.luogu.com.cn/training/441063)
## 6.1 模运算
## 6.2 快速幂
## 6.3 矩阵的应用
### 例6.1 [Fibonacci](http://poj.org/problem?id=3070)
### 例6.2 [Matrix Power Series](http://poj.org/problem?id=3233)
### 例6.3 [Cow Relays](http://poj.org/problem?id=3613)
#### 课后习题:
[P1349 广义斐波那契数列](https://www.luogu.com.cn/problem/P1349)
[P1939 矩阵加速（数列）](https://www.luogu.com.cn/problem/P1939)
[P1306 斐波那契公约数](https://www.luogu.com.cn/problem/P1306)
[P2044 [NOI2012] 随机数生成器](https://www.luogu.com.cn/problem/P2044)
[P5175 数列](https://www.luogu.com.cn/problem/P5175)
[P3390 【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390)
[P1939 矩阵加速（数列）](https://www.luogu.com.cn/problem/P1939)
[P4783 【模板】矩阵求逆](https://www.luogu.com.cn/problem/P4783)
[P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962)
[P1349 广义斐波那契数列](https://www.luogu.com.cn/problem/P1349)
[P4000 斐波那契数列](https://www.luogu.com.cn/problem/P4000)
[P3758 [TJOI2017] 可乐](https://www.luogu.com.cn/problem/P3758)
[P4967 黑暗打击](https://www.luogu.com.cn/problem/P4967)
[P5343 【XR-1】分块](https://www.luogu.com.cn/problem/P5343)
[P5303 [GXOI/GZOI2019] 逼死强迫症](https://www.luogu.com.cn/problem/P5303)
[hdu 4990 Reading comprehension](https://acm.hdu.edu.cn/showproblem.php?pid=4990)
[hdu 4565 So Easy!](https://acm.hdu.edu.cn/showproblem.php?pid=4565)
[hdu 4549 M斐波那契数列](https://acm.hdu.edu.cn/showproblem.php?pid=4549)
[hdu 4686 Arc of Dream](https://acm.hdu.edu.cn/showproblem.php?pid=4686)
[233 Matrix](https://acm.hdu.edu.cn/showproblem.php?pid=5015)
[hdu 2157 How many ways??](https://acm.hdu.edu.cn/showproblem.php?pid=2157)
## 6.4 高斯消元
### 例6.4 [【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)
### 例6.5 [Painter's Problem](http://poj.org/problem?id=1681)
### 例6.6 [Gambler Bo](https://acm.hdu.edu.cn/showproblem.php?pid=5755)
#### 课后习题:
[P3389 【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)
[P4387 【深基15.习9】验证栈序列](https://www.luogu.com.cn/problem/P4387)
[P2447 [SDOI2010] 外星千足虫](https://www.luogu.com.cn/problem/P2447)
[P4035 [JSOI2008] 球形空间产生器](https://www.luogu.com.cn/problem/P4035)
[P5516 [MtOI2019] 小铃的烦恼](https://www.luogu.com.cn/problem/P5516)
[P4111 [HEOI2015] 小 Z 的房间](https://www.luogu.com.cn/problem/P4111)
[P4457 [BJOI2018] 治疗之雨](https://www.luogu.com.cn/problem/P4457)
[poj 2947 Widget Factory](http://poj.org/problem?id=2947)
[poj 1487 Single-Player Games](http://poj.org/problem?id=1487)
[poj 2065 SETI](http://poj.org/problem?id=2065)
[poj 1166 The Clocks](http://poj.org/problem?id=1166)
[poj 2965 The Pilots Brothers' refrigerator](http://poj.org/problem?id=2965)
## 6.5 异或线性基
### 例6.7 [【模板】线性基](https://www.luogu.com.cn/problem/P3812)
### 例6.8 [XOR](https://acm.hdu.edu.cn/showproblem.php?pid=3949)
#### 课后习题:
[P3857 [TJOI2008] 彩灯](https://www.luogu.com.cn/problem/P3857)
[P4570 [BJWC2011] 元素](https://www.luogu.com.cn/problem/P4570)
[P3292 [SCOI2016] 幸运数字](https://www.luogu.com.cn/problem/P3292)
[P4151 [WC2011] 最大XOR和路径](https://www.luogu.com.cn/problem/P4151)
## 6.6 0/1分数规划
### 例6.9 [Dropping tests](http://poj.org/problem?id=2976)
### 例6.10 [[USACO18OPEN] Talent Show G](https://www.luogu.com.cn/problem/P4377)
#### 课后习题:
[P3199 [HNOI2009] 最小圈](https://www.luogu.com.cn/problem/P3199)
[P3288 [SCOI2014] 方伯伯运椰子](https://www.luogu.com.cn/problem/P3288)
[P3705 [SDOI2017] 新生舞会](https://www.luogu.com.cn/problem/P3705)
[P4322 [JSOI2016] 最佳团体](https://www.luogu.com.cn/problem/P4322)
## 6.7 GCD和LCM
### 例6.11 [[SDOI2009] SuperGCD](https://www.luogu.com.cn/problem/P2152)
### 习题:
[hdu 5019 Revenge of GCD](https://acm.hdu.edu.cn/showproblem.php?pid=5019)
[hdu 2503 a/b + c/d](https://acm.hdu.edu.cn/showproblem.php?pid=2503)
[hdu 2504 又见GCD](https://acm.hdu.edu.cn/showproblem.php?pid=2504)
[hdu 4497 GCD and LCM](https://acm.hdu.edu.cn/showproblem.php?pid=4497)
[hdu 2104 hide handkerchief](https://acm.hdu.edu.cn/showproblem.php?pid=2104)
[hdu 3092 Least common multiple](https://acm.hdu.edu.cn/showproblem.php?pid=3092)
[hdu 5970 最大公约数](https://acm.hdu.edu.cn/showproblem.php?pid=5970)
[hdu 5584 LCM Walk](https://acm.hdu.edu.cn/showproblem.php?pid=5584)
[P2568 GCD](https://www.luogu.com.cn/problem/P2568)
[P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
[P1890 gcd区间](https://www.luogu.com.cn/problem/P1890)
[P5435 基于值域预处理的快速 GCD](https://www.luogu.com.cn/problem/P5435)
[P5436 【XR-2】缘分](https://www.luogu.com.cn/problem/P5436)
[P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题](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 [NOIP2009 提高组] Hankson 的趣味题](https://www.luogu.com.cn/problem/P1072)
[poj 1722 SUBTRACT](http://poj.org/problem?id=1722)
[poj 2685 Numeral System](http://poj.org/problem?id=2685)
[poj 3101 Astronomy](http://poj.org/problem?id=3101)
[poj 2429 GCD & LCM Inverse](http://poj.org/problem?id=2429)
### 例6.12 [【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)
### 例6.13 [Pagodas](https://acm.hdu.edu.cn/showproblem.php?pid=5512)
### 例6.14 [Uniform Generator](http://poj.org/problem?id=1597)
## 6.8 线性丢番图方程
### 例6.15 [How Many Points?](https://lightoj.com/problem/how-many-points)
### 例6.16 [Area](http://poj.org/problem?id=1265)
### 例6.17 [青蛙的约会](https://www.luogu.com.cn/problem/P1516)
### 例6.18 [最大体积](https://lx.lanqiao.cn/problem.page?gpid=T261)
## 6.9 同余
### 例6.19 [[NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)
### 例6.20 [C Looooops](http://poj.org/problem?id=2115)
### 例6.21 [【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811)
### 例6.22 [A/B](https://acm.hdu.edu.cn/showproblem.php?pid=1576)
### 例6.23 [Detachment](https://acm.hdu.edu.cn/showproblem.php?pid=5976)
### 例6.24 [【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.com.cn/problem/P4777)
#### 课后习题:
[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 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)
[P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目](https://www.luogu.com.cn/problem/P3951)
[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)
[poj 2305 Basic remains](http://poj.org/problem?id=2305)
[poj 2635 The Embarrassed Cryptographer](http://poj.org/problem?id=2635)
[poj 3292 Semi-prime H-numbers](http://poj.org/problem?id=3292)
[poj 1845 Sumdiv](http://poj.org/problem?id=1845)
[poj 2115 C Looooops](http://poj.org/problem?id=2115)
[poj 1006 Biorhythms](http://poj.org/problem?id=1006)
## 6.10 素数(质数)
### 例6.25 [How many prime numbers](https://acm.hdu.edu.cn/showproblem.php?pid=2138)
#### 课后习题:
[P4718 【模板】Pollard-Rho](https://www.luogu.com.cn/problem/P4718)
[P1075 [NOIP2012 普及组] 质因数分解](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)
## 6.11 威尔逊定理
### 例6.26 [Zball in Tina Town](https://acm.hdu.edu.cn/showproblem.php?pid=5391)
### 例6.27 [YAPTCHA](https://acm.hdu.edu.cn/showproblem.php?pid=2973)
### 例6.28 [Fansblog](https://acm.hdu.edu.cn/showproblem.php?pid=6608)
## 6.12 积性函数
## 6.13 欧拉函数
### 6.29 [[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)
[P5221 Product](https://www.luogu.com.cn/problem/P5221)
## 6.14 整除分块(数论分块)
#### 课后习题:
[P1829 [国家集训队] Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
[P2261 [CQOI2007] 余数求和](https://www.luogu.com.cn/problem/P2261)
[P3935 Calculating](https://www.luogu.com.cn/problem/P3935)
## 6.15 狄利克雷卷积
## 6.16 莫比乌斯函数和莫比乌斯反演
#### 课后习题
[P3172 [CQOI2015] 选数](https://www.luogu.com.cn/problem/P3172)
[P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522)
[P3455 [POI2007] ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
[P3327 [SDOI2015] 约数个数和](https://www.luogu.com.cn/problem/P3327)
[P1829 [国家集训队] Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
[P4619 [SDOI2018] 旧试题](https://www.luogu.com.cn/problem/P4619)
[P3704 [SDOI2017] 数字表格](https://www.luogu.com.cn/problem/P3704)
[P5518 [MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题](https://www.luogu.com.cn/problem/P5518)
## 6.17 杜教筛
### 例6.30 [【模板】杜教筛](https://www.luogu.com.cn/problem/P4213)
### 额外未提及的习题:
[P3803 【模板】多项式乘法（FFT）](https://www.luogu.com.cn/problem/P3803)
[P1919 【模板】(A * B) Problem 升级版（FFT 快速傅里叶变换）](https://www.luogu.com.cn/problem/P1919)
[P4238 【模板】多项式乘法逆](https://www.luogu.com.cn/problem/P4238)
[P4245 【模板】任意模数多项式乘法](https://www.luogu.com.cn/problem/P4245)
[P4512 【模板】多项式除法](https://www.luogu.com.cn/problem/P4512)
[P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)](https://www.luogu.com.cn/problem/P4717)
[P4721 【模板】分治 FFT](https://www.luogu.com.cn/problem/P4721)
[P4725 【模板】多项式对数函数（多项式 ln）](https://www.luogu.com.cn/problem/P4725)
[P4726 【模板】多项式指数函数（多项式 exp）](https://www.luogu.com.cn/problem/P4726)
[P4781 【模板】拉格朗日插值](https://www.luogu.com.cn/problem/P4781)
[P5050 【模板】多项式多点求值](https://www.luogu.com.cn/problem/P5050)
[P5158 【模板】多项式快速插值](https://www.luogu.com.cn/problem/P5158)
[P5205 【模板】多项式开根](https://www.luogu.com.cn/problem/P5205)
[P5245 【模板】多项式快速幂](https://www.luogu.com.cn/problem/P5245)
[P5273 【模板】多项式幂函数（加强版）](https://www.luogu.com.cn/problem/P5273)
[P5282 【模板】快速阶乘算法](https://www.luogu.com.cn/problem/P5282)
[P5373 【模板】多项式复合函数](https://www.luogu.com.cn/problem/P5373)
[P5383 普通多项式转下降幂多项式](https://www.luogu.com.cn/problem/P5383)
[P5393 下降幂多项式转普通多项式](https://www.luogu.com.cn/problem/P5393)
[P5394 【模板】下降幂多项式乘法](https://www.luogu.com.cn/problem/P5394)
[P3338 [ZJOI2014] 力](https://www.luogu.com.cn/problem/P3338)
[P3723 [AH2017/HNOI2017] 礼物](https://www.luogu.com.cn/problem/P3723)
[P5437 【XR-2】约定](https://www.luogu.com.cn/problem/P5437)
[P5293 [HNOI2019] 白兔之舞](https://www.luogu.com.cn/problem/P5293)
[P5432 A/B Problem（高精度除法）](https://www.luogu.com.cn/problem/P5432)
[P5472 [NOI2019] 斗主地](https://www.luogu.com.cn/problem/P5472)
[P5577 [CmdOI2019] 算力训练](https://www.luogu.com.cn/problem/P5577)
[P4525 【模板】自适应辛普森法 1](https://www.luogu.com.cn/problem/P4525)
[P5104 红包发红包](https://www.luogu.com.cn/problem/P5104)
[P1850 [NOIP2016 提高组] 换教室](https://www.luogu.com.cn/problem/P1850)
[P3830 [SHOI2012] 随机树](https://www.luogu.com.cn/problem/P3830)
[P4564 [CTSC2018] 假面](https://www.luogu.com.cn/problem/P4564)
[P2473 [SCOI2008] 奖励关](https://www.luogu.com.cn/problem/P2473)
[P2221 [HAOI2012] 高速公路](https://www.luogu.com.cn/problem/P2221)
[P3239 [HNOI2015] 亚瑟王](https://www.luogu.com.cn/problem/P3239)
[P3750 [六省联考 2017] 分手是祝愿](https://www.luogu.com.cn/problem/P3750)
[P4284 [SHOI2014] 概率充电器](https://www.luogu.com.cn/problem/P4284)
[P5249 [LnOI2019] 加特林轮盘赌](https://www.luogu.com.cn/problem/P5249)
[P2081 [NOI2012] 迷失游乐园](https://www.luogu.com.cn/problem/P2081)
[P3343 [ZJOI2015] 地震后的幻想乡](https://www.luogu.com.cn/problem/P3343)
[P3600 随机数生成器](https://www.luogu.com.cn/problem/P3600)
[P5326 [ZJOI2019] 开关](https://www.luogu.com.cn/problem/P5326)
[poj 2151 Check the difficulty of problems](http://poj.org/problem?id=2151)
[poj 3071 Football](http://poj.org/problem?id=3071)
[poj 3440 Coin Toss](http://poj.org/problem?id=3440)