hdu - 1576 - A/B（乘法逆元）

题意：求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;
}