A/B（HDU - 1576，费马小定理 + 乘法逆元）

一.题目链接：

HDU-1576

二.题目大意：

要求 (A / B) % 9973，但由于 A 很大，我们只给出 n (n = A % 9973)

(我们给定的A必能被B整除，且gcd(B,9973) = 1).

三.分析：

费马小定理：假如 P 是质数，且 gcd(B，P) = 1，则  % P = 1.

由此可推出：如果 B 为整数，且 P 为质数，那么  % P = 1.

再乘法逆元可得：（A / B）% P = A *  % P.

其实没啥好分析的，我就是想存个板子.

四.代码实现：

    #include <set>
    #include <map>
    #include <ctime>
    #include <queue>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #define eps 1e-6
    #define PI acos(-1.0)
    #define ll long long int
    using namespace std;

    ll power(ll a, ll b, ll c)
    {
        ll sum = 1;
        while(b)
        {
            if(b & 1)
                sum = (sum % c * a % c) % c;
            a = (a % c * a % c) % c;
            b >>= 1;
        }
        return sum % c;
    }

    int main()
    {
        int T;
        ll n, b;
        ll p = 9973;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%lld %lld", &n, &b);
            printf("%lld\n", n * power(b, p - 2, p) % p);
        }
        return 0;
    }