原题链接
https://ac.nowcoder.com/acm/problem/264714
思路分析
快速幂求逆元
费马小定理： a MOD − 1 ≡ 1 ( m o d M O D ) a^{\text{MOD}-1} \equiv 1 \pmod{MOD} aMOD−1≡1(modMOD)，可以转换为 a ⋅ a MOD − 2 ≡ 1 ( m o d M O D ) ① a \cdot a ^{\text{MOD}-2} \equiv 1 \pmod{MOD} \text{ ①} a⋅aMOD−2≡1(modMOD) ①。
题目中： x ⋅ Q ≡ P ( m o d M O D ) x \cdot Q \equiv P \pmod{MOD} x⋅Q≡P(modMOD)，可以转换为 x P ⋅ Q ≡ 1 ( m o d M O D ) ② \frac{x}{P} \cdot Q \equiv 1 \pmod{MOD} \text{ ②} Px⋅Q≡1(modMOD) ②
由①、②可推导出： x P ≡ Q MOD − 2 ( m o d M O D ) \frac{x}{P} \equiv Q^{\text{MOD}-2} \pmod{MOD} Px≡QMOD−2(modMOD) ， 可以转换为 $
// 快速幂 (x: 底数 y: 指数 p: MOD)
LL quickPower(LL x, LL y, LL p) {
LL result = 1;
x = x % p;
while (y > 0) {
if (y & 1)
result = (result * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return result;
}
// Q^(MOD - 2)
LL Q_inv = quickPower(Q, MOD - 2, MOD);
// x = P * Q^(MOD - 2) % MOD
LL x = (P * Q_inv) % MOD;
