题目理解

我们需要计算 $\frac{a}{b} \bmod p$，其中 $p = 10^9+7$，$a$ 和 $b$ 可能是大整数（最多 $5000$ 位十进制数），并且 不保证 $\frac{a}{b}$ 合法。

这里的「合法」是指：

1. $b \not\equiv 0 \pmod{p}$，即 $b$ 在模 $p$ 下有乘法逆元。
2. 如果有解，解是唯一的（在模 $p$ 意义下）。

「不合法」的情况就是 $b \equiv 0 \pmod{p}$，此时分母在模 $p$ 下没有逆元，因此分数在模 $p$ 下无定义。

核心思路

题目提示已经给出：
计算 $\frac{a}{b} \bmod p$ 等价于计算 $a \times b^{-1} \bmod p$，其中 $b^{-1}$ 是 $b$ 模 $p$ 的乘法逆元。

乘法逆元

对于质数 $p$ 和 $b \not\equiv 0 \pmod{p}$，$b^{-1} \bmod p$ 存在且唯一，满足：

可以用 费马小定理 求：

因为 $p$ 是质数。

负数处理

题目说明：$(-A) \bmod p = -(A \bmod p)$，这里是指结果的符号在模运算外处理。
实际上在模 $p$ 运算中，我们通常将负数转为 $[0, p-1]$ 范围内的数。
但在输出时，如果 $a/b$ 是负数，那么 $a \times b^{-1} \bmod p$ 在 $[0, p-1]$ 范围内会是正数，所以需要根据 $a,b$ 的符号来判断最终输出的正负号。

更好的做法是：

1. 将 $a$ 和 $b$ 分别模 $p$ 得到 $a'$ 和 $b'$（在 $[0, p-1]$ 内）。
2. 如果 $b' = 0$，则无解。
3. 否则计算 $inv = b'^{p-2} \bmod p$。
4. 计算 $ans = a' \times inv \bmod p$。
5. 如果原分数 $\frac{a}{b}$ 是负数（即 $a,b$ 异号），且 $ans \neq 0$，则输出 $-(p - ans)$？
   不对，题目要求 $(-A) \bmod p = -(A \bmod p)$，所以如果 $\frac{a}{b}$ 是负数，那么结果应是 $-(|a/b| \bmod p)$ 的形式。
   实际上更简单的做法是：计算 $a \bmod p$ 和 $b \bmod p$ 时保留符号信息（C/Java 取模规则），然后计算 $(a \bmod p) \times inv \bmod p$ 得到的结果可能为负数，直接输出这个负数即可。

实现步骤

1. 读入 $a, b$
   由于 $a,b$ 可能达到 $10^{5000}$，需要用字符串读入。

2. 判断 $b \bmod p$ 是否为 0
   大数模 $p$ 可以通过逐位计算得到：
   设 $res = 0$，对每一位数字 $d$ 做 $res = (res \times 10 + d) \bmod p$。

3. 如果 $b \bmod p = 0$
   输出 No Solution!。

4. 否则
   计算 $a \bmod p$ 和 $b \bmod p$（注意负数取模规则：x % p 在 C/Java 中对负数得到 $[-p+1, 0]$ 的值）。

   然后计算 $b^{-1} = (b \bmod p)^{p-2} \bmod p$（快速幂）。

   计算 $ans = (a \bmod p) \times b^{-1} \bmod p$。

   这里 $a \bmod p$ 可能为负数，所以乘完之后再模 $p$ 会得到负数（在 $[-p+1, p-1]$ 范围内），直接输出即可。

样例验证

样例 1

$a=1, b=2$
$b \bmod p = 2 \neq 0$
$b^{-1} = 2^{p-2} \bmod p = 500000004$
$ans = 1 \times 500000004 \bmod p = 500000004$
输出正确。

样例 2

$a=1, b=-2$
$b \bmod p = -2$（在 C/Java 中 $-2 \bmod p = -2$）
$b^{-1} = (-2)^{p-2} \bmod p$，因为 $p$ 是质数，$(-2)^{p-2} \equiv -(2^{p-2}) \pmod{p}$，所以 $b^{-1} = -(500000004)$
$ans = 1 \times (-500000004) \bmod p = -500000004$
输出正确。

注意事项

1. 大数取模时，负数要先判断符号，然后对绝对值取模，再恢复符号。
2. 快速幂计算 $b^{p-2} \bmod p$ 时，$b$ 可能为负数，要处理好。
3. 最终结果在 C/Java 取模规则下直接输出，不需要调整到 $[0, p-1]$。

时间复杂度

• 大数取模：$O(\text{len}(a) + \text{len}(b))$
• 快速幂：$O(\log p)$，$p \approx 10^9$，约 $30$ 次迭代。

总复杂度对于 $5000$ 位大数完全可行。

总结

这道题本质是 大数取模 + 费马小定理求逆元，关键在于：

1. 理解分数模质数的定义。
2. 正确处理大数和负数取模。
3. 判断无解条件 $b \equiv 0 \pmod{p}$。

只要思路清晰，实现起来并不复杂。