模运算与快速幂
基础概念
基通俗讲解
模运算就是“除以 p 取余数”，结果永远在 0…p-1。快速幂用“平方倍增”把 aⁿ 从乘 n 次降到 log n 次，常配合取模防溢出。
核心必背考点
背直接默写拿分
(a+b)%p = (a%p+b%p)%p(a-b)%p = ((a%p-b%p)+p)%p（防负）(a*b)%p = (a%p*b%p)%p- 快速幂：
aⁿ = (a²)ⁿ/²，n 偶用平方，n 奇多乘一个 a。
高频难点 / 拉分考点
难考场极易丢分
减法取模出现负数：必须 +p 再 %p 修正。初赛填空题常考此处。
出题陷阱
坑文字套路
(a^b)%p ≠ (a%p)^(b%p)！指数不能先取模（除非用欧拉定理，初赛不要求）。- 除法不能直接分配模，需逆元（超纲，初赛不考）。
90分高分技巧
技速算捷径
求 aⁿ%p：用快速幂模板；小 n 直接算。选择题可特殊值法代入 a=2,n=3,p=5 验证公式。
梯度真题
基础(7+8)%5 的值
15%5=0。
▍解析：答案 0。
中档(2*9)%5 的值
18%5=3。
▍解析：答案 3。
压轴2^10 mod 7
快速幂：2^10=1024，1024%7=2。
| 1 | long long powmod(long long a,long long n,long long p){ |
| 2 | long long r=1; a%=p; |
| 3 | while(n){ |
| 4 | if(n&1) r=r*a%p; |
| 5 | a=a*a%p; n>>=1; |
| 6 | } |
| 7 | return r; |
| 8 | } |
▍解析：答案 2。
记忆口诀
技📌 记忆口诀
“加减乘都可分配，减法要加 p 防负；指数不可先取模，平方倍增快速幂。”
📝 本节自测共 6 题
做完点「提交本节自测」即时判分；单选 / 多选 / 填空混合，答错可一键收入错题本。
(7 + 5) mod 3 的值是？
✅ 正确答案：A
12 mod 3 = 0。
在 C++ 中，-1 % 3 的结果通常是？
✅ 正确答案：A
C++ 向零取整，余数的符号与被除数相同，得 -1。
快速幂中反复取模的主要目的是？
✅ 正确答案：A
边算边 mod 使数值保持小，防止溢出。
用扩展欧几里得求 gcd(30, 12) = ____ 。（填空） 填空题 难
✅ 正确答案：6
30 与 12 的最大公约数是 6。
关于质数，下列说法正确的有哪些？（多选） 多选题 难
✅ 正确答案：ABD
2 是唯偶质数、质数无穷多、合数可质因子分解；1 既不是质数也不是合数。
下列哪些方法可用来求最大公约数？（多选） 多选题 中
✅ 正确答案：ABC
欧几里得 / 更相减损 / 扩欧都能求 gcd；快速幂用于幂运算。