初等数论

题单介绍

2020/8/12 不定期更新 --- 适合数论初学者，难度从普及-到省选。 下方为算法标签，想自己思考的请右转[题目列表](https://www.luogu.com.cn/training/17933#problems) 当然有些题也可以乱搞 ~~比如暴力过CRT~~ --- ## 质数 ### 判定 AT1476 素数判定 P5736 【深基7.例2】质数筛 ### 埃氏筛 & 线性筛 P3383 【模板】线性筛素数 P3912 素数个数 P1865 A % B Problem UVA10140 Prime Distance ### 其他 P1463 [POI2002][HAOI2007]反素数 ## 约数 ### GCD & LCM P4057 [Code+#1]晨跑 P1029 最大公约数和最小公倍数问题 P5436 【XR-2】缘分 ### 其他 P1403 [AHOI2005]约数研究 ## 欧拉函数 P2158 [SDOI2008]仪仗队 P2303 [SDOI2012] Longge 的问题 （按gcd分类） P2568 GCD （按gcd分类） P2155 [SDOI2008]沙拉公主的困惑 ## 同余 ### 裴蜀定理 P4549 【模板】裴蜀定理 ### 扩欧 P1082 同余方程 P1516 青蛙的约会 P1292 倒酒 P2421 [NOI2002]荒岛野人 ### 逆元 P3811 【模板】乘法逆元 P5431 【模板】乘法逆元2 P2054 [AHOI2005]洗牌 ### （扩展）欧拉定理 & 费马小定理 P5091 【模板】扩展欧拉定理 P4139 上帝与集合的正确用法 ### （扩展）中国剩余定理 P1495 【模板】中国剩余定理(CRT)/曹冲养猪 P3868 [TJOI2009]猜数字 P4777 【模板】扩展中国剩余定理（EXCRT）

题目列表

  • [ARC044A] 素数判定
  • [NOIP 2012 普及组] 质因数分解
  • 【深基7.例2】质数筛
  • 【模板】线性筛素数
  • 素数个数
  • A % B Problem
  • 素数密度
  • Prime Distance
  • [POI 2001 R1 / HAOI2007] 反素数
  • [Code+#1] 晨跑
  • [NOIP 2001 普及组] 最大公约数和最小公倍数问题
  • 【XR-2】缘分
  • [AHOI2005] 约数研究
  • 【模板】裴蜀定理
  • [NOIP 2012 提高组] 同余方程
  • 倒酒
  • [NOIP 2017 提高组] 小凯的疑惑
  • 青蛙的约会
  • [NOI2002] 荒岛野人
  • 【模板】模意义下的乘法逆元
  • 【模板】模意义下的乘法逆元 2
  • 回忆京都
  • [AHOI2005] 洗牌
  • [SDOI2008] 仪仗队
  • [SDOI2012] Longge 的问题
  • GCD
  • [SDOI2008] 沙拉公主的困惑
  • 【模板】扩展欧拉定理
  • 上帝与集合的正确用法
  • 【模板】中国剩余定理（CRT）/ 曹冲养猪
  • [TJOI2009] 猜数字
  • 【模板】扩展中国剩余定理（EXCRT）