歐幾里得算法：
遞歸版本：

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

迭代版本：

int gcd(int a,int b)
{
    while(b!=0)
    {
        int r=b;
        b=a%b;
        a=r;
    }
    return a;
}

擴展歐幾里德算法：
基本算法：對于不完全為 0 的非負整數(shù) a，b，gcd（a，b）表示 a，b 的最大公約數(shù)，必然存在整數(shù)對 x，y ，使得 gcd（a，b）=ax+by。

證明：設 a>b。
　　1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
　　2，ab!=0 時
　　設 ax1+by1=gcd(a,b);
　　bx2+(a mod b)y2=gcd(b,a mod b);
　　根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
　　則:ax1+by1=bx2+(a mod b)y2;
　　即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)*by2;
　　根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int res=exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return res;
}

擴展歐幾里德算法的應用主要有以下三方面：
（1）求解不定方程；
（2）求解模線性方程（線性同余方程）；
（3）求解模的逆元;

（1）使用擴展歐幾里德算法解決不定方程的辦法：
對于不定整數(shù)方程a*x+b*y=c，若 c mod Gcd(x, y)=0,則該方程存在整數(shù)解，否則不存在整數(shù)解。 上面已經(jīng)列出找一個整數(shù)解的方法，在找到 a*x+ b*y = Gcd(a,b)的一組解x0,y0后，
a*x+b*y = Gcd(a, b)的其他整數(shù)解滿足：
x = x0 + b/Gcd(a, b) * t
y = y0 - a/Gcd(a, b) * t(其中t為任意整數(shù))
因為a*x+b*y=a(x0 + b/Gcd(a, b) * t)+b(y0 - a/Gcd(a, b) * t)=Gcd(a,b)

其中，最小的正整數(shù)x為: x=x0%( b/Gcd(a, b) )
最小的正整數(shù)y: y=y0%( a/Gcd(a, b) )

至于ax+by=c的整數(shù)解，只需將a*x+b*y= Gcd(a,b)的每個解乘上 c/Gcd(a,b) 即可。

用擴展歐幾里得算法解不定方程ax+by=c;

bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //初解
  /*
  x=x+b/(gcd(a,b))*t;//其他解
  y=y-a/(gcd(a,b))*t;
  t為任意整數(shù)
  */
    return true;
}

(2)用擴展歐幾里德算法求解模線性方程的方法：
同余方程 ax≡b (mod n),即（a*x-b) mod n=0;推出a*x+n*y=b;所以轉(zhuǎn)化為求不定方程a*x+n*y=Gcd(a,n)。
如果b%(Gcd(a,n))!=0,那么方程無整數(shù)解;否則求出初解x0,然而初值還要乘以b/Gcd(a,n),即x=x0*b/Gcd(a,n)才是方程a*x+n*y=b的解
而其他整數(shù)解則滿足：
x(i) = x + b/Gcd(a, b) * t
y(i) = y - a/Gcd(a, b) * t (其中t為任意整數(shù))

bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //特解
    for(i=1;i<d;i++)
        printf("%d\n",(x0+i*(n/d))%n);
    return true;
}

（3）用歐幾里德算法求模的逆元：
乘法逆元:如果a*x≡1 (mod p),且gcd(a,p)=1（a與p互質(zhì)），則稱a關(guān)于模p的乘法逆元為x。
它的同余方程ax+py=gcd(a,p)=1,而1%1==0,所以肯定有解

LL exgcd(LL a,ll b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL reverseMod(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);//求初解x
    //其他解為x(i) = x+b/Gcd(a, b)*t=x+mod/1*t=x+mod*t
    while(x<0) x+=mod;//求出一個x>0的逆元
    return x;

} 

( 4 )用費馬小定理求乘法逆元。
由費馬小定理a^(p-1)≡ 1(mod p)(p為素數(shù))，稍作變形即是 a*a^(p-2)≡ 1(mod p)，是不是發(fā)現(xiàn)了，a^(p-2)即是a的逆元，這個可以用快速冪來求。

typedef long long LL;
LL fast_multi(LL a,LL b,LL mod)
{
    LL res=0,base=a;
    while(b)
    {
        if(b&1) res=(res+base)%mod;
        b>>=1;
        base=(base+base)%mod;
    }
    return res;
}
LL pow_mod(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1) res=fast_multi(res,base,mod);
        base=fast_multi(base,base,mod);
        b>>=1;
    }
    return res;
}//b關(guān)于對mod取模的逆元為pow_mod(b,mod-2,mod);

題目：求(a/b)%mod。
題解：先求出b的逆元，然后結(jié)果為(a*(b^-1) )%mod，b^-1指b關(guān)于對mod取模運算的逆元

#include<stdio.h>
#include <string.h>
using namespace std;
const long long mod=9973;//一個素數(shù)
typedef long long LL;
LL fast_multi(LL a,LL b,LL mod)
{
    LL res=0,base=a;
    while(b)
    {
        if(b&1) res=(res+base)%mod;
        b>>=1;
        base=(base+base)%mod;
    }
    return res;
}
LL pow_mod(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1) res=fast_multi(res,base,mod);
        base=fast_multi(base,base,mod);
        b>>=1;
    }
    return res;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    LL gcd=exgcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL reverseMod(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    while(x<0) x+=mod;
    return x;

}
int main()
{
    int n;
    LL a,b,x;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lld%lld",&a,&b);
        x=reverseMod(b,mod);
        printf("%lld\n",fast_multi(a,x,mod));//擴展歐里幾德
        printf("%lld\n",fast_multi(a,pow_mod(b,mod-2,mod),mod));//費馬小定理
    }
}