hdu 1576 (A/B)

这个题的关键是求逆元，根据扩展欧几里德算法：
代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod=9973;
void exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-(a/b)*y;
}
LL multi(LL a,LL b,LL m)
{
    a%=m;
    LL ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%m;
            b--;
        }
        b/=2;
        ans=(a+a)%m;
    }
    return ans;
}
int main()
{
    LL a,b,m,n,x,y,t;
    cin>>m;
    while(m--)
    {
        cin>>n>>b;
        exgcd(b,mod,x,y);
        LL ans=(x%mod+mod)%mod;//逆元
        LL sum=(n*(ans%mod))%mod;
        cout<<sum<<endl;;
    }
    return 0;
}