『算法-ACM 竞赛-数学-数论』HDU1576 A _ B(逆元）

问题描述
要求（A / B）％9973，但由于 A 很大，我们只被告知 n（n = A％9973）（我们给定的 A 必能被 B 整除，且 gcd（B，9973）= 1）。

输入项
数据的第一行是一个 T，表示有 T 组数据。
每组数据有两个数 n（0 <= n <9973）和 B（1 <= B <= 10 ^ 9）。

输出量
对应每组数据输出（A / B）％9973。

样本输入
2
1000 53
87 123456789

样本输出
7922
6060

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef  long long INT;
const INT p = 9973;
INT ex_gcd(INT a, INT b,INT &x, INT &y)
{
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    INT d = ex_gcd(b , a % b,x,y);
    INT tmp =x;
    x = y;
    y = tmp - a / b * y;
    return d;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
        INT n, b,x,y;
        cin >> n >> b;
        ex_gcd(b, p,x,y);
        cout << (x % p * n % p + p) % p << endl;
    }
    return 0;
}