ユークリッドを開拓して逆元のテンプレートを求めます(C++版)

逆元は実は逆数の1つの普及(私の理解)に相当して、例えばA/BはA乗Bの逆元に相当して、つまり逆数で、模nの情況の下で簡単な逆数だけではありませんこのような情況は拡張ユークリッドで逆元を求めて、具体的な証明はまだよく分かりません.お先におんぶしましょう
hdu 1576題はA%MODとMODとBに(A/B)%MODを求めることを意味し、それはA%MODが実際には既知のAに相当することが知られているが、Bを直接除算することはできないので、Bを乗じた逆元に相当するので、問題はBを求める逆元に転化する.

#include 
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}
ll inv(ll a,ll m){
    ll x,y;
    ll d=exgcd(a,m,x,y);
    if(d==1){
        //    
        return (x%m+m)%m;
    }
    return -1;
}
ll n,b;
int t;
const ll MOD=9973;
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&b);
        ll c=inv(b,MOD);
        printf("%lld
",n*c%MOD);
    }
    return 0;
}