算法竞赛避坑指南：一文搞懂“乘法逆元”与“有理数（分数）取模”（附 C++ / Python 极简实战模板）

在刷题时，有些题目会要求把分数形式的答案对 $10^9+7$ 取模。理论答案明明是 $3.5$，提交时却不能输出小数，而要输出一个看起来毫无规律的大整数。题面里出现的 $x$、$y$ 和 $y^{-1}$ 又是什么意思？

这里用到的知识叫乘法逆元，对应的计算方式叫有理数取模或分数取模。理解它之后，模意义下的除法就能转成乘法来做。

一、题目里的 $x$、$y$ 和逆元 $y^{-1}$ 是什么？

有些题目会出现类似这样的输出要求：

可以证明答案能写成最简分数 $\frac{x}{y}$，其中 $x$、$y$ 是整数，并且 $y \not\equiv 0 \pmod{10^9+7}$。请输出 $x \cdot y^{-1} \pmod{10^9+7}$。

这里的 $x$ 和 $y$ 不是输入变量，而是我们推导出的最终答案的分子和分母。例如答案 $3.5$ 可以写成 $\frac{7}{2}$，此时 $x=7$、$y=2$。

在普通算术里，除以 $y$ 等于乘以 $\frac{1}{y}$。但模运算中不能直接做普通除法，所以我们要找一个整数 $y^{-1}$，使得：

$$y \cdot y^{-1} \equiv 1 \pmod P$$

这个 $y^{-1}$ 就是 $y$ 在模 $P$ 意义下的乘法逆元。因此：

$$\frac{x}{y} \pmod P ;=; x \cdot y^{-1} \pmod P$$

要特别注意，逆元不一定存在。一般来说，$y$ 在模 $P$ 下有逆元，当且仅当 $\gcd(y,P)=1$。当 $P$ 是质数时，这个条件等价于 $y$ 不能被 $P$ 整除。题目保证分母不为 $0 \pmod P$，就是在保证这里可以求逆元。

二、为什么 $\frac{7}{2}$ 会变成 `500000007`？

以模数 $P=10^9+7$ 为例。因为 $P$ 是质数，根据费马小定理，只要 $y$ 不被 $P$ 整除，就有：

$$y^{-1} \equiv y^{P-2} \pmod P$$

先求 $2$ 的逆元：

$$2^{-1} \equiv 500000004 \pmod{10^9+7}$$

因为 $2\times500000004=1000000008\equiv1\pmod{1000000007}$。所以：

$$\frac{7}{2} \equiv 7\times500000004 \equiv 3500000028 \equiv 500000007 \pmod{1000000007}$$

因此，分数 $\frac{7}{2}$ 对 $10^9+7$ 取模的结果是 500000007。这个结果表示模意义下与 $\frac{7}{2}$ 等价的整数，不是把 $3.5$ 四舍五入或转换成小数。

再看一个例子：

$$5+\frac{1}{6}=\frac{31}{6}$$

对 $10^9+7$ 取模后，结果是 166666673。

三、C++ 快速幂、逆元和分数模板

费马小定理把求逆元转成了快速幂。下面这套模板适用于质数模数，并要求传给 inv(y) 的 $y$ 不被 MOD 整除。竞赛中常见的质数模数有 $10^9+7$ 和 $998244353$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL MOD = 1e9 + 7;

// 计算 a^b % MOD
LL qpow(LL a, LL b) {
	LL res = 1;
	a = (a % MOD + MOD) % MOD;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

// 求 y 的乘法逆元：要求 MOD 是质数，且 y % MOD != 0
LL inv(LL y) {
	return qpow(y, MOD - 2);
}

// 计算 x / y（模 MOD 意义下）
LL frac(LL x, LL y) {
	return (x % MOD + MOD) % MOD * inv(y) % MOD;
}

上面的 qpow 使用二进制快速幂，时间复杂度是 $O(\log MOD)$。对于这里常见的 $10^9+7$ 或 $998244353$，两个小于 MOD 的数相乘不会超过 long long 的范围；如果题目模数更大，就要另外考虑乘法溢出。

四、分数转成模数后，四则运算怎么写？

用 frac(x, y) 得到的是模 $MOD$ 下的整数表示。只要中间结果都保持在 $[0, MOD)$，后续运算仍然按模数处理即可，不需要先把分数通分成普通分数。

1. 除法：乘以分母的逆元

C++ 的整数除法会截去小数部分，所以 7 / 2 得到的是 3。要表示模意义下的 $\frac{7}{2}$，写成：

1 2	LL a = frac(7, 2); LL b = frac(1, 6);

这里的分母都必须满足可以求逆元的条件。

2. 加法：直接相加后取模

例如 $2+\frac{3}{2}$：

1	LL ans = (2 + frac(3, 2)) % MOD;

分数加分数也一样。例如 $\frac{1}{2}+\frac{1}{3}$，可以直接写：

1
2
3

LL a = frac(1, 2);
LL b = frac(1, 3);
LL ans = (a + b) % MOD;

这与先通分再计算 $\frac{5}{6}$ 的模结果相同，前提仍是分母在模 MOD 下可逆。

3. 乘法：直接相乘后取模

1 2	LL res1 = 3 * frac(1, 2) % MOD; LL res2 = frac(1, 2) * frac(1, 3) % MOD;

第二行计算的结果与 frac(1, 6) 相同。

4. 减法：加上 `MOD` 再取模

两个已经规范到 $[0, MOD)$ 的数相减可能为负数，所以减法可以写成：

1 2	LL a = frac(1, 3); LL res = (1 - a + MOD) % MOD; // 等价于 frac(2, 3)

这个写法假设 a 和被减数已经是规范的模数范围内的值。如果连续减去多个数，每一步都要及时取模并保持结果非负。

五、完整的 C++ 与 Python 示例

1. C++ 完整演示代码

下面的程序演示前面的例子和分数混合加减：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL MOD = 1e9 + 7;

LL qpow(LL a, LL b) {
	LL res = 1;
	a = (a % MOD + MOD) % MOD;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

LL inv(LL y) {
	return qpow(y, MOD - 2);
}

LL frac(LL x, LL y) {
	return (x % MOD + MOD) % MOD * inv(y) % MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// 2 + 3 * (1 / 2) = 7 / 2
	LL half = frac(1, 2);
	LL ans1 = (2 + 3 * half % MOD) % MOD;
	cout << ans1 << '\n'; // 500000007

	// 5 + 1 / 6 = 31 / 6
	LL ans2 = (5 + frac(1, 6)) % MOD;
	cout << ans2 << '\n'; // 166666673

	// 1 / 2 + 1 / 3 - 1 / 6 = 2 / 3
	LL a = frac(1, 2);
	LL b = frac(1, 3);
	LL c = frac(1, 6);
	LL res = (a + b) % MOD;
	res = (res - c + MOD) % MOD;
	cout << res << ' ' << frac(2, 3) << '\n';

	return 0;
}

2. Python 极简模板

Python 3.8 及以上版本还可以用三参数 pow(y, -1, MOD) 直接求逆元；要求 $y$ 与 MOD 互质。下面仍使用费马小定理的写法，方便和 C++ 模板对应：

MOD = 10**9 + 7  # 根据题目修改模数

# 要求 MOD 是质数，且 y % MOD != 0
def inv(y):
    return pow(y, MOD - 2, MOD)

# 计算 x / y（模 MOD 意义下）
def frac(x, y):
    return x % MOD * inv(y) % MOD

ans1 = (2 + 3 * frac(1, 2)) % MOD
ans2 = (5 + frac(1, 6)) % MOD
res = (frac(1, 2) + frac(1, 3) - frac(1, 6)) % MOD

print(ans1)               # 500000007
print(ans2)               # 166666673
print(res == frac(2, 3))  # True