HDU 1576 A/B(逆元拡張ユークリッドを求める)

【タイトルリンク】:click here~~
【問題の大意】:
(A/B)%9973が要求されるが、Aが大きいため、n(n=A%9973)のみが与えられる(与えられたAは必ずBによって除去され、gcd(B,9973)=1).
【考え方】この問題にはいろいろな方法があります.
法一:逆元で解決すればいい.
コード:

/*  
* Problem: HDU No.1576 
* Running time: 0MS  
* Complier: C++  
* Author: javaherongwei 
* Create Time: 20:51 2015/9/2    
*/  
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b;
LL mod=9973;
LL poww(LL a,LL b)
{
    LL res=a,ans=1;
    while(b)
    {
        if(b&1) ans=ans*res%mod;
        res=res*res%mod;
        b>>=1;
    }
    return ans;
}
LL niyuan(LL a)
{
    return poww(a,mod-2);
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&a,&b);
        printf("%lld
",a*niyuan(b)%mod);
    } return 0;
}

法二:拡張ユークリッド:
【考え方】:
(A/B)%9973=Kとすると、A/B=k+9973*xであるため、A=kB+9973*x*Bであり、またA%9973=nであるため、kB%9973=nであるため、kB=n+9973*yである(k/n)B+(-y/n)*9973=gcd(B,9973)=1拡張ユークリッドでk/nを求める
コード:

/*
* Problem: HDU No.1576
* Running time: 15MS
* Complier: C++
* Author: javaherongwei
* Create Time: 21:07 2015/9/2    
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,x,y;
LL mod=9973;
void ext_gcd(LL &a,LL &b,LL n,LL m) // Extended Euclidean Algorithm
{
    if(m==0)
    {
        a=1;
        b=0;
        return ;
    }
    ext_gcd(a,b,m,n%m);
    LL d=a;
    a=b;
    b=d-n/m*b;
}

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&a,&b);
        ext_gcd(x,y,b,mod);
        x*=a;
        x=(x%mod+mod)%mod;
        printf("%lld
",x);
    } return 0;
}