HDU 1576 A/B：模逆元求分數取模

題目

計算 (A/B) mod 9973，其中 B 與 9973 互質（9973 為質數）。多測試用例。

數學

模質數 p 下，B^{-1} ≡ B^{p-2} (mod p)（費馬小定理）。或用擴展歐幾裡得算法求 B*x + p*y = 1，則 x 為逆元。答案 = A * B^{-1} mod p。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 9973;
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a%b, x1, y1);
    x = y1; y = x1 - (a/b)*y1;
    return g;
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long A, B; scanf("%lld%lld", &A, &B);
        long long x, y; ext_gcd(B, MOD, x, y);
        x = (x % MOD + MOD) % MOD;
        printf("%lld\n", A % MOD * x % MOD);
    }
    return 0;
}