取模看起来只是一个很普通的运算,但真正写进代码以后,负数、乘法溢出和模意义下的除法都很容易出错。特别是看到分式时,不能直接把普通除法搬进模运算,而是要先判断分母有没有逆元。

这篇文章从模运算与同余开始,接着介绍扩展欧几里得、线性同余方程、乘法逆元和欧拉定理,最后通过七道例题把这些内容连起来。

模运算与同余

取模的定义

对于整数aa和正整数mm,一定存在唯一的整数q,rq,r,满足:

a=qm+r,0≤r<ma=qm+r,\qquad 0\le r<m

其中qq是商,rr是aa除以mm得到的余数,记作:

r=a mod mr=a\bmod m

数学中的余数始终位于[0,m−1][0,m-1]。但C++中的 % 更接近“取余”,结果与被除数同号,因此:

1
cout << -3 % 5; // -3

而数学意义下的−3 mod 5-3\bmod5应当等于22。如果需要把结果规范到[0,m−1][0,m-1],先取模,再处理负数即可:

1
2
3
i64 x = -3, mod = 5;
x %= mod;
if (x < 0) x += mod;

例如:

−3≡2(mod5)-3\equiv2\pmod5

同余式:符号≡\equiv表示同余。例如x≡y(modp)x\equiv y\pmod p表示xx与yy除以pp所得的余数相同;上式中,−3-3与22除以55所得的余数都是22。

处理以后x=2x=2。

模运算的基本性质

设m>0m>0,加法、减法和乘法都可以在运算过程中取模:

(a+b) mod m=((a mod m)+(b mod m)) mod m(a+b)\bmod m=((a\bmod m)+(b\bmod m))\bmod m

(a−b) mod m=((a mod m)−(b mod m)) mod m(a-b)\bmod m=((a\bmod m)-(b\bmod m))\bmod m

(ab) mod m=((a mod m)(b mod m)) mod m(ab)\bmod m=((a\bmod m)(b\bmod m))\bmod m

以加法为例,设a=q1m+r1,b=q2m+r2a=q_1m+r_1,b=q_2m+r_2,那么:

a+b=(q1+q2)m+(r1+r2)a+b=(q_1+q_2)m+(r_1+r_2)

前面的整倍数部分不会影响余数,只需要继续计算(r1+r2) mod m(r_1+r_2)\bmod m。减法和乘法同理。

减法最容易漏掉负数。例如:

(6−3) mod 5=3(6-3)\bmod5=3

但分别取余以后得到1−3=−21-3=-2,还要再规范一次。

实际写题时,模数经常固定为109+710^9+7。如果a,ba,b已经被规范到[0,mod−1][0,mod-1],可以把它设为默认模数:

1
2
3
4
5
const int MOD = 1e9 + 7;

int addM(int a, int b, int mod = MOD) { return (a += b) >= mod ? a - mod : a; }
int subM(int a, int b, int mod = MOD) { return (a -= b) < 0 ? a + mod : a; }
int mulM(int a, int b, int mod = MOD) { return (i64)a * b % mod; }

调用常用模数时不必反复传入MOD,遇到其他较小模数时再显式传入第三个参数。addM和subM只修正一次,是因为a,ba,b已经在合法余数范围内;若输入可能为负数或超过模数,应先取模并处理负数。乘法先转成i64,避免a×ba\times b在取模以前溢出。

这份简洁模板适用于模数不超过109+710^9+7的常见题目。如果模数来自输入并且可能接近i64上限,就不能继续使用int,应改回i64并用i128承接中间结果。后文遇到动态模数时会保留显式的mod参数。

除法不能照搬上面的运算律。例如:

(12÷3) mod 6=4(12\div3)\bmod6=4

但12 mod 6=012\bmod6=0,先取模再除以33只会得到00。模意义下的除法需要乘法逆元,后面会专门说明。

同余

如果a,ba,b除以mm得到的余数相同,就称a,ba,b模mm同余,记作:

a≡b(modm)a\equiv b\pmod m

同余还可以写成更方便证明的形式:

a≡b(modm)  ⟺  m∣(a−b)a\equiv b\pmod m\iff m\mid(a-b)

它满足下面这些基本性质:

  1. 自反性:a≡a(modm)a\equiv a\pmod m;
  2. 对称性:若a≡b(modm)a\equiv b\pmod m,则b≡a(modm)b\equiv a\pmod m;
  3. 传递性:若a≡b(modm)a\equiv b\pmod m且b≡c(modm)b\equiv c\pmod m,则a≡c(modm)a\equiv c\pmod m;
  4. 若a≡b(modm),c≡d(modm)a\equiv b\pmod m,c\equiv d\pmod m,则a+c≡b+d(modm)a+c\equiv b+d\pmod m;
  5. 若a≡b(modm),c≡d(modm)a\equiv b\pmod m,c\equiv d\pmod m,则ac≡bd(modm)ac\equiv bd\pmod m;
  6. 若a≡b(modm)a\equiv b\pmod m,则ak≡bk(modm)a^k\equiv b^k\pmod m,其中kk为非负整数。

同余式不能随意约分。若:

ac≡bc(modm)ac\equiv bc\pmod m

只有当gcd⁡(c,m)=1\gcd(c,m)=1时,才能直接约去cc并保持模数不变。一般情况下,设d=gcd⁡(c,m)d=\gcd(c,m),只能得到:

a≡b(modm/d)a\equiv b\pmod{m/d}

这也是模意义下的除法需要先判断互质条件的原因。

扩展欧几里得算法

裴蜀定理

对于不同时为00的整数a,ba,b,一定存在整数x,yx,y,使得:

ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

这就是裴蜀定理。更进一步,线性方程:

ax+by=cax+by=c

存在整数解,当且仅当:

gcd⁡(a,b)∣c\gcd(a,b)\mid c

普通欧几里得算法只能求出最大公因数,扩展欧几里得算法还会顺便求出一组满足裴蜀等式的x,yx,y。

从 gcd 推到 exgcd

欧几里得算法的递推式为:

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)

假设递归到下一层以后,已经求出:

bx1+(a mod b)y1=gbx_1+(a\bmod b)y_1=g

又因为:

a mod b=a−⌊ab⌋ba\bmod b=a-\left\lfloor\frac ab\right\rfloor b

代回原式可得:

ay1+b(x1−⌊ab⌋y1)=gay_1+b\left(x_1-\left\lfloor\frac ab\right\rfloor y_1\right)=g

因此当前这一层的系数为:

x=y1,y=x1−⌊ab⌋y1x=y_1,\qquad y=x_1-\left\lfloor\frac ab\right\rfloor y_1

对应代码如下:

1
2
3
4
5
6
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) { x = 1; y = 0; return a; }
i64 g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}

递归边界是b=0b=0,此时:

a×1+0×0=aa\times1+0\times0=a

回溯时再按照上面的式子逐层还原系数。整个过程与欧几里得算法的递归层数相同,对于非负且不同时为00的a,ba,b,时间复杂度为O(log⁡max⁡(a,b))O(\log\max(a,b))。

线性方程的全部解

设g=gcd⁡(a,b)g=\gcd(a,b),并且 exgcd 求出:

ax0+by0=gax_0+by_0=g

如果g∤cg\nmid c,方程没有整数解;否则将两边同时乘c/gc/g,得到一组特解:

x1=x0cg,y1=y0cgx_1=x_0\frac cg,\qquad y_1=y_0\frac cg

全部整数解为:

x=x1+kbg,k∈Zx=x_1+k\frac bg,\qquad k\in\mathbb Z

y=y1−kag,k∈Zy=y_1-k\frac ag,\qquad k\in\mathbb Z

如果题目只要求任意一组解,输出x1,y1x_1,y_1即可;如果要求最小正整数解或限制解的范围,就需要继续调整kk。

线性同余方程

形如:

ax≡b(modm)ax\equiv b\pmod m

的式子称为线性同余方程。根据同余的定义,它等价于存在整数yy,满足:

ax+my=bax+my=b

设d=gcd⁡(a,m)d=\gcd(a,m)。由裴蜀定理可知,方程有解当且仅当:

d∣bd\mid b

如果d∤bd\nmid b,直接判定无解;否则同时除以dd:

adx≡bd(modm/d)\frac adx\equiv\frac bd\pmod{m/d}

此时gcd⁡(a/d,m/d)=1\gcd(a/d,m/d)=1,所以a/da/d在模m/dm/d意义下存在逆元。设x0x_0是一个解,那么原方程在模mm意义下共有dd个不同的解:

x=x0+kmd,k=0,1,…,d−1x=x_0+k\frac md,\qquad k=0,1,\ldots,d-1

如果只要求最小非负解,只需要把x0x_0规范到[0,m/d−1][0,m/d-1]。这一步很容易写错:解的周期是m/dm/d,不是原来的mm。

乘法逆元与欧拉定理

乘法逆元

若存在整数xx满足:

ax≡1(modm)ax\equiv1\pmod m

就称xx是aa在模mm意义下的乘法逆元,记作a−1a^{-1}。

逆元存在的充要条件是:

gcd⁡(a,m)=1\gcd(a,m)=1

如果逆元存在,那么根据同余的定义,存在整数yy使得:

ax+my=1ax+my=1

这正是裴蜀等式,所以可以使用 exgcd 求出xx。反过来,如果d=gcd⁡(a,m)>1d=\gcd(a,m)>1,那么dd同时整除axax和mymy,不可能整除右边的11,逆元也就不存在。

求出xx以后,还要把它规范到[0,m−1][0,m-1]:

1
2
3
i64 x, y;
i64 g = exgcd(a, mod, x, y);
if (g == 1) { x %= mod; if (x < 0) x += mod; }

有了逆元,模意义下的除法就可以改写为乘法:

ab≡a⋅b−1(modm)\frac ab\equiv a\cdot b^{-1}\pmod m

但前提仍然是gcd⁡(b,m)=1\gcd(b,m)=1。如果分母没有逆元,就不能使用这个式子。

欧拉函数与欧拉定理

欧拉函数φ(m)\varphi(m)表示11到mm中与mm互质的整数个数。若mm的不同质因子为p1,p2,…,pkp_1,p_2,\ldots,p_k,那么:

φ(m)=m∏i=1k(1−1pi)\varphi(m)=m\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)

直接分解质因数即可在O(m)O(\sqrt m)时间内求出φ(m)\varphi(m)。

当gcd⁡(a,m)=1\gcd(a,m)=1时,欧拉定理给出:

aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod m

因此可以对指数按φ(m)\varphi(m)取模:

ab≡ab mod φ(m)(modm)a^b\equiv a^{b\bmod\varphi(m)}\pmod m

互质条件不能省略。若gcd⁡(a,m)>1\gcd(a,m)>1,直接把指数对φ(m)\varphi(m)取模可能改变答案。

费马小定理

当pp是质数时,φ(p)=p−1\varphi(p)=p-1。若p∤ap\nmid a,欧拉定理可以写成:

ap−1≡1(modp)a^{p-1}\equiv1\pmod p

这就是费马小定理。将两边拆出一个aa:

a⋅ap−2≡1(modp)a\cdot a^{p-2}\equiv1\pmod p

所以aa在模pp意义下的逆元为:

a−1≡ap−2(modp)a^{-1}\equiv a^{p-2}\pmod p

指数p−2p-2通常很大,需要用快速幂在O(log⁡p)O(\log p)时间内计算。

扩展欧几里得和费马小定理都可以求单个逆元,但适用条件不同:

方法 模数要求 时间复杂度 适合场景
扩展欧几里得 gcd⁡(a,m)=1\gcd(a,m)=1 O(log⁡m)O(\log m) 一般模数下的单个逆元
费马小定理 pp必须是质数且p∤ap\nmid a O(log⁡p)O(\log p) 质数模数下的单个逆元

如果要求模质数pp下11到nn的全部逆元,并且n<pn<p,还可以线性递推:

invi=(p−⌊pi⌋)invp mod i mod pinv_i=\left(p-\left\lfloor\frac pi\right\rfloor\right)inv_{p\bmod i}\bmod p

1
2
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = mulM(mod - mod / i, inv[mod % i], mod);

这个写法可以在O(n)O(n)时间内求出全部逆元,不过它依赖pp为质数且n<pn<p,不能不看条件直接套用。

扩展欧拉定理

普通欧拉定理要求a,ma,m互质。若题目没有这个保证,但指数bb很大,可以使用扩展欧拉定理。

当b<φ(m)b<\varphi(m)时,指数本身不需要处理;当b≥φ(m)b\ge\varphi(m)时:

ab≡ab mod φ(m)+φ(m)(modm)a^b\equiv a^{b\bmod\varphi(m)+\varphi(m)}\pmod m

这里多加的φ(m)\varphi(m)不能随手删掉。它保证底数与模数不互质时,约去的指数仍然足够大。

如果bb大到必须用字符串保存,就在读入每一位时计算b mod φ(m)b\bmod\varphi(m),同时记录bb是否已经达到φ(m)\varphi(m)。这样不需要真正存下bb的数值。

常见模型与例题

下面七道题从快速幂开始,依次覆盖扩展欧几里得、线性同余方程、乘法逆元、费马小定理、扩展欧拉定理和任意模数下的等比数列求和。

题目 核心知识点 需要注意的地方
洛谷 P1226 快速幂 乘法溢出与输出格式
Codeforces 7C 扩展欧几里得 负数系数与无解判断
洛谷 P1516 线性同余方程 有解条件与最小非负解
洛谷 P1082 乘法逆元 将负数解规范为最小正解
AtCoder ABC156 D 费马小定理、组合数 nn很大,不能预处理到nn
洛谷 P5091 扩展欧拉定理 指数很长且模数不一定为质数
AtCoder ABC293 E 等比数列取模 模数不保证为质数,不能直接相除

例题一:洛谷 P1226 快速幂

题目链接:洛谷 P1226【模板】快速幂

给定a,b,pa,b,p,求ab mod pa^b\bmod p。

朴素做法连续乘bb次,时间复杂度为O(b)O(b)。当bb很大时,可以把它拆成二进制。例如:

11=(1011)2=8+2+111=(1011)_2=8+2+1

于是:

a11=a8⋅a2⋅aa^{11}=a^8\cdot a^2\cdot a

从低位到高位枚举bb的二进制位。当前位为11时,把当前的aa乘入答案;每处理完一位,就让aa平方并把bb右移一位。

1
2
3
4
5
6
7
i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; }
i64 qpow(i64 a, i64 b, i64 mod) {
i64 ans = 1 % mod;
for (a %= mod; b; b >>= 1, a = mulM(a, a, mod))
if (b & 1) ans = mulM(ans, a, mod);
return ans;
}

循环次数等于bb的二进制位数,因此时间复杂度为O(log⁡b)O(\log b),空间复杂度为O(1)O(1)。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; }
i64 qpow(i64 a, i64 b, i64 mod) {
i64 ans = 1 % mod;
for (a %= mod; b; b >>= 1, a = mulM(a, a, mod))
if (b & 1) ans = mulM(ans, a, mod);
return ans;
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, b, p;
cin >> a >> b >> p;
cout << a << '^' << b << " mod " << p << '=' << qpow(a, b, p) << '\n';
return 0;
}

例题二:Codeforces 7C

题目链接:Codeforces 7C Line

题目给出A,B,CA,B,C,要求寻找一组整数x,yx,y,满足:

Ax+By+C=0Ax+By+C=0

移项以后得到:

Ax+By=−CAx+By=-C

设g=gcd⁡(A,B)g=\gcd(A,B),方程有整数解当且仅当g∣(−C)g\mid(-C)。为了让 exgcd 的递归过程更稳定,可以先对∣A∣,∣B∣|A|,|B|求系数,再按照原来的符号修正x,yx,y。

若 exgcd 求出:

∣A∣x0+∣B∣y0=g|A|x_0+|B|y_0=g

将x0,y0x_0,y_0同时乘(−C)/g(-C)/g,就得到原方程的一组解。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) { x = 1; y = 0; return a; }
i64 g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, b, c, x, y;
cin >> a >> b >> c;
c = -c;
i64 g = exgcd(abs(a), abs(b), x, y);
if (c % g) { cout << -1 << '\n'; return 0; }
x *= c / g; y *= c / g;
if (a < 0) x = -x;
if (b < 0) y = -y;
cout << x << ' ' << y << '\n';
return 0;
}

这道题中A,B,CA,B,C都可能为负数,AA或BB还可能等于00。只要保证传入 exgcd 的两个数非负,并在最后恢复符号,就不需要为这些情况分别写一套算法。时间复杂度为O(log⁡max⁡(∣A∣,∣B∣))O(\log\max(|A|,|B|)),空间复杂度为O(log⁡max⁡(∣A∣,∣B∣))O(\log\max(|A|,|B|))。

例题三:洛谷 P1516 青蛙的约会

题目链接:洛谷 P1516 青蛙的约会

两只青蛙在长度为LL的环上移动。它们的起点分别为x,yx,y,每次分别移动m,nm,n,求最少经过多少次移动才能相遇。

经过tt次移动以后,两只青蛙的位置分别为:

x+tm,y+tnx+tm,\qquad y+tn

要在环上相遇,两者模LL同余:

x+tm≡y+tn(modL)x+tm\equiv y+tn\pmod L

移项得到:

(m−n)t≡y−x(modL)(m-n)t\equiv y-x\pmod L

设a=m−n,b=y−x,d=gcd⁡(a,L)a=m-n,b=y-x,d=\gcd(a,L)。当d∤bd\nmid b时无解;否则使用 exgcd 求出a/da/d在模L/dL/d意义下的逆元,就能得到tt的最小非负解。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) { x = 1; y = 0; return a; }
i64 g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 x, y, m, n, l;
cin >> x >> y >> m >> n >> l;
i64 a = m - n, b = y - x, p, q;
i64 d = exgcd(abs(a), l, p, q);
if (b % d) { cout << "Impossible\n"; return 0; }
if (a < 0) p = -p;
i128 ans = (i128)p * (b / d) % (l / d);
if (ans < 0) ans += l / d;
cout << (i64)ans << '\n';
return 0;
}

这里最关键的是模数要缩小为L/dL/d。时间复杂度和空间复杂度均为O(log⁡L)O(\log L)。

例题四:洛谷 P1082 同余方程

题目链接:洛谷 P1082 同余方程

题目要求同余方程:

ax≡1(modb)ax\equiv1\pmod b

的最小正整数解。根据同余的定义,它等价于存在整数yy,满足:

ax+by=1ax+by=1

输入保证方程有解,因此gcd⁡(a,b)=1\gcd(a,b)=1。使用 exgcd 求出一组x,yx,y以后,xx可能为负数,但所有解在模bb意义下属于同一个剩余类。将它规范为:

x←(x mod b+b) mod bx\leftarrow(x\bmod b+b)\bmod b

就能得到[0,b−1][0,b-1]中的唯一代表。由于b≥2b\ge2且逆元存在,这个结果不会等于00,因此它正是题目要求的最小正整数解。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) { x = 1; y = 0; return a; }
i64 g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
x %= b;
if (x < 0) x += b;
cout << x << '\n';
return 0;
}

求单个逆元只需要一次扩展欧几里得,时间复杂度和空间复杂度均为O(log⁡b)O(\log b)。

例题五:AtCoder ABC156 D

题目链接:AtCoder ABC156 D Bouquet

有nn种不同的花,每种只有一朵。需要选择至少一朵组成花束,但不能恰好选择aa朵或bb朵,求方案数对109+710^9+7取模的结果。

所有非空子集共有:

2n−12^n-1

再减去大小恰好为a,ba,b的集合:

ans=2n−1−(na)−(nb)ans=2^n-1-\binom na-\binom nb

这里nn最大达到10910^9,不能预处理到nn的阶乘。但a,b≤2×105a,b\le2\times10^5,可以直接使用:

(nk)=n(n−1)⋯(n−k+1)k!\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}

模数109+710^9+7是质数,并且k!k!不被模数整除,所以:

(k!)−1≡(k!)mod−2(modmod)(k!)^{-1}\equiv(k!)^{mod-2}\pmod{mod}

分子和分母分别计算,再用费马小定理求分母的逆元即可。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
const int MOD = 1e9 + 7;

int subM(int a, int b, int mod = MOD) { return (a -= b) < 0 ? a + mod : a; }
int mulM(int a, int b, int mod = MOD) { return (i64)a * b % mod; }
int qpow(int a, i64 b, int mod = MOD) {
int ans = 1;
for (; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod);
return ans;
}
int comb(i64 n, int m) {
int a = 1, b = 1;
for (int i = 1; i <= m; i++) { a = mulM(a, (n - i + 1) % MOD); b = mulM(b, i); }
return mulM(a, qpow(b, MOD - 2));
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n; int a, b;
cin >> n >> a >> b;
int ans = subM(subM(subM(qpow(2, n), 1), comb(n, a)), comb(n, b));
cout << ans << '\n';
return 0;
}

快速幂和两次组合数计算的总时间复杂度为O(a+b+log⁡n+log⁡MOD)O(a+b+\log n+\log MOD),空间复杂度为O(1)O(1)。

例题六:洛谷 P5091 扩展欧拉定理

题目链接:洛谷 P5091【模板】扩展欧拉定理

给定a,m,ba,m,b,求ab mod ma^b\bmod m。其中mm不保证为质数,a,ma,m也不保证互质,并且bb可能有两千万位,无法使用整数类型保存。

先分解mm的质因数,求出φ(m)\varphi(m)。随后逐位读取bb,同时维护:

  1. b mod φ(m)b\bmod\varphi(m);
  2. bb是否已经达到φ(m)\varphi(m)。

若b<φ(m)b<\varphi(m),快速幂的指数仍然是bb;否则将指数改为:

b mod φ(m)+φ(m)b\bmod\varphi(m)+\varphi(m)

这样既保留了扩展欧拉定理需要的大小信息,也把真正参与快速幂的指数压到了2φ(m)2\varphi(m)以内。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; }
i64 phi(i64 n) {
i64 ans = n;
for (i64 p = 2; p * p <= n; p++) if (n % p == 0) {
ans = ans / p * (p - 1);
while (n % p == 0) n /= p;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
i64 qpow(i64 a, i64 b, i64 mod) {
i64 ans = 1 % mod;
for (a %= mod; b; b >>= 1, a = mulM(a, a, mod))
if (b & 1) ans = mulM(ans, a, mod);
return ans;
}
pair<i64, bool> parse(const string &s, i64 mod) {
i64 rem = 0, val = 0; bool large = false;
for (char c : s) {
int x = c - '0'; rem = (rem * 10 + x) % mod;
if (!large) { val = val * 10 + x; if (val >= mod) large = true; }
}
return {rem, large};
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, mod; string b;
cin >> a >> mod >> b;
i64 ph = phi(mod);
auto [e, large] = parse(b, ph);
if (large) e += ph;
cout << qpow(a, e, mod) << '\n';
return 0;
}

设bb的十进制位数为LL。求欧拉函数需要O(m)O(\sqrt m),处理指数需要O(L)O(L),最后一次快速幂需要O(log⁡φ(m))O(\log\varphi(m));空间复杂度为O(L)O(L)。

例题七:AtCoder ABC293 E

题目链接:AtCoder ABC293 E Geometric Progression

给定A,X,MA,X,M,求:

SX=∑i=0X−1Ai mod MS_X=\sum_{i=0}^{X-1}A^i\bmod M

普通等比数列公式为:

SX=AX−1A−1S_X=\frac{A^X-1}{A-1}

但题目没有保证MM是质数,也没有保证gcd⁡(A−1,M)=1\gcd(A-1,M)=1,所以A−1A-1不一定存在逆元,不能直接使用这个分式。

可以在分治过程中同时维护:

Pn=An mod M,Sn=∑i=0n−1Ai mod MP_n=A^n\bmod M,\qquad S_n=\sum_{i=0}^{n-1}A^i\bmod M

设已经得到Pk,SkP_k,S_k,那么:

P2k=Pk2(modM)P_{2k}=P_k^2\pmod M

S2k=Sk+AkSk=Sk(1+Pk)(modM)S_{2k}=S_k+A^kS_k=S_k(1+P_k)\pmod M

如果n=2k+1n=2k+1,再补上最后一项A2kA^{2k}:

P2k+1=P2kA(modM)P_{2k+1}=P_{2k}A\pmod M

S2k+1=S2k+P2k(modM)S_{2k+1}=S_{2k}+P_{2k}\pmod M

每次递归都把nn减半,不需要任何除法,也不要求MM为质数。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 addM(i64 a, i64 b, i64 mod) { i128 x = (i128)a + b; return x >= mod ? x - mod : x; }
i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; }
pair<i64, i64> calc(i64 a, i64 n, i64 mod) {
if (!n) return {1 % mod, 0};
auto [p, s] = calc(a, n >> 1, mod);
i64 p2 = mulM(p, p, mod), s2 = mulM(s, addM(p, 1 % mod, mod), mod);
if (!(n & 1)) return {p2, s2};
return {mulM(p2, a, mod), addM(s2, p2, mod)};
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, x, mod;
cin >> a >> x >> mod;
cout << calc(a % mod, x, mod).second << '\n';
return 0;
}

递归深度为O(log⁡X)O(\log X),每层只进行常数次模乘,时间复杂度和空间复杂度均为O(log⁡X)O(\log X)。

如果还想继续练习,线性同余方程可以做AtCoder ABC186 E Throne,欧拉定理可以做AtCoder ABC222 G 222。Codeforces 710D Two Arithmetic Progressions和Codeforces 906D Power Tower会进一步涉及联立同余方程与欧拉函数链,适合放到后面再做。

总结与常见问题

常见问题

  • 为什么 C++ 中负数取模以后还可能是负数? C++ 的 % 保留被除数的符号;如果需要数学意义下的最小非负剩余,应先令 x%=mod,再在x<0x<0时加上modmod。
  • 为什么乘法以后再取模仍然可能出错? 如果 a*b 先发生整数溢出,后面的取模已经无法挽回。模数较大时应先转成 i128,或使用专门的快速乘。
  • 同余式两边能不能直接约分? 只有被约掉的数与模数互质时,才能保持原模数不变;否则需要缩小模数。
  • 线性同余方程什么时候有解? ax≡b(modm)ax\equiv b\pmod m有解,当且仅当gcd⁡(a,m)∣b\gcd(a,m)\mid b。约去最大公因数以后,解的周期是m/gcd⁡(a,m)m/\gcd(a,m)。
  • 逆元什么时候存在? aa在模mm意义下存在逆元,当且仅当gcd⁡(a,m)=1\gcd(a,m)=1。
  • 扩展欧几里得和费马小定理应该用哪一个? 一般模数使用扩展欧几里得;模数确定为质数时,可以用快速幂计算ap−2a^{p-2}。
  • 费马小定理能不能用于合数模数? 不能直接使用am−2a^{m-2}求逆元。模数不是质数时应先判断互质,再使用扩展欧几里得。
  • 指数能不能直接对φ(m)\varphi(m)取模? 只有a,ma,m互质时才能直接使用欧拉定理;不保证互质时,需要保留指数是否达到φ(m)\varphi(m)的信息,再使用扩展欧拉定理。
  • 为什么求出的逆元可能是负数? 扩展欧几里得给出的是一组整数解,负数同样合法。对xx取模,并在x<0x<0时加上模数,就能得到最小非负代表。
  • 等比数列为什么不能直接套分式? 分母A−1A-1在当前模数下可能没有逆元。不能确认互质时,应改用分治或矩阵快速幂。

复杂度分析

操作 时间复杂度 空间复杂度
单次加、减、乘与取模 O(1)O(1) O(1)O(1)
快速幂 O(log⁡b)O(\log b) O(1)O(1)
欧几里得算法 O(log⁡max⁡(a,b))O(\log\max(a,b)) O(1)O(1)
扩展欧几里得 O(log⁡max⁡(a,b))O(\log\max(a,b)) O(log⁡max⁡(a,b))O(\log\max(a,b))
求解线性同余方程 O(log⁡max⁡(∣a∣,m))O(\log\max(\lvert a\rvert,m)) O(log⁡max⁡(∣a∣,m))O(\log\max(\lvert a\rvert,m))
扩展欧几里得求单个逆元 O(log⁡m)O(\log m) O(log⁡m)O(\log m)
费马小定理求单个逆元 O(log⁡p)O(\log p) O(1)O(1)
线性求11到nn的逆元 O(n)O(n) O(n)O(n)
质因数分解求φ(m)\varphi(m) O(m)O(\sqrt m) O(1)O(1)
扩展欧拉处理LL位指数 O(m+L+log⁡φ(m))O(\sqrt m+L+\log\varphi(m)) O(L)O(L)
分治计算等比数列和 O(log⁡X)O(\log X) O(log⁡X)O(\log X)

系列文章

  1. 基础数论入门
  2. 模意义下的数和运算