扩展欧几里得 hdu 1576

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1576

不知道扩展欧几里得的同学可以参考：https://blog.csdn.net/zhjchengfeng5/article/details/7786595

我的推理：

这图片是真的大啊...

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<cstdio>
using namespace std;
#define eps 1e-8
typedef long long ll;
#define INF 0x3f3f3f3f
ll n,B,d,x,y;
int t;
void ex_gcd(ll a,ll b ,ll &d,ll &x,ll &y)
{
    if(!b)
    {
        d=a;
        x=1;
        y=0;
        return;
    }
    ex_gcd(b,a%b,d,y,x);
    y-=x*(a/b);
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>B;
        ex_gcd(B,9973,d,x,y);
        x*=n;    //这里d一定是1，因为gcd（B，9973）==1 
        x%=9973;
        if(x<0)    //在这里如果<变成<=也可以ac，但是我觉得不能加，否则应该会出现x=9973的情况 
        x+=9973;
        cout<<x<<endl;
    }
    return 0;
}