学步园

题意：求A / B % 9973，但只给出 n = A % 9973 和 B(0 <= n < 9973, 1 <= B <= 10^9)。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1576

——>>求逆元练手。。

#include <cstdio>

typedef long long LL;

const int MOD = 9973;

LL n, B;

void Read()
{
    scanf("%I64d%I64d", &n, &B);
}

void Gcd(LL a, LL b, LL& d, LL& x, LL& y)
{
    if (!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        Gcd(b, a % b, d, y, x);
        y -= a / b * x;
    }
}

LL Inv(int a, int n)
{
    LL ret = 0, d, y;

    Gcd(a, n, d, ret, y);

    return d == 1 ? (ret + n) % n : -1;
}

void Solve()
{
    printf("%I64d\n", n * Inv(B, MOD) % MOD);
}

int main()
{
    int T;

    scanf("%d", &T);
    while (T--)
    {
        Read();
        Solve();
    }

    return 0;
}