数学--数论--HDU1576 A / B(逆元）

#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;
}