歐幾里得算法：
遞歸版本：
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;
}
擴(kuò)展歐幾里德算法：
基本算法：對(duì)于不完全為 0 的非負(fù)整數(shù) a狰贯，b也搓，gcd（a赏廓，b）表示 a，b 的最大公約數(shù)傍妒，必然存在整數(shù)對(duì) x幔摸，y ，使得 gcd（a颤练，b）=ax+by既忆。
證明：設(shè) a>b。
1昔案，顯然當(dāng) b=0尿贫，gcd（a，b）=a踏揣。此時(shí) x=1庆亡，y=0；
2捞稿，ab!=0 時(shí)
設(shè) 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;
}
擴(kuò)展歐幾里德算法的應(yīng)用主要有以下三方面：
（1）求解不定方程娱局；
（2）求解模線性方程（線性同余方程）彰亥；
（3）求解模的逆元;
（1）使用擴(kuò)展歐幾里德算法解決不定方程的辦法：
對(duì)于不定整數(shù)方程a*x+b*y=c，若 c mod Gcd(x, y)=0,則該方程存在整數(shù)解衰齐，否則不存在整數(shù)解任斋。 上面已經(jīng)列出找一個(gè)整數(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ù))
因?yàn)閍*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)的每個(gè)解乘上 c/Gcd(a,b) 即可抹缕。
用擴(kuò)展歐幾里得算法解不定方程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)用擴(kuò)展歐幾里德算法求解模線性方程的方法：
同余方程 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,那么方程無(wú)整數(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;//求出一個(gè)x>0的逆元
return x;
}
( 4 )用費(fèi)馬小定理求乘法逆元趴俘。
由費(fèi)馬小定理a^(p-1)≡ 1(mod p)(p為素?cái)?shù))，稍作變形即是 a*a^(p-2)≡ 1(mod p)奏赘，是不是發(fā)現(xiàn)了寥闪，a^(p-2)即是a的逆元，這個(gè)可以用快速冪來(lái)求磨淌。
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)于對(duì)mod取模的逆元為pow_mod(b,mod-2,mod);
題目：求(a/b)%mod疲憋。
題解：先求出b的逆元，然后結(jié)果為(a*(b^-1) )%mod伦糯，b^-1指b關(guān)于對(duì)mod取模運(yùn)算的逆元
#include<stdio.h>
#include <string.h>
using namespace std;
const long long mod=9973;//一個(gè)素?cái)?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));//擴(kuò)展歐里幾德
printf("%lld\n",fast_multi(a,pow_mod(b,mod-2,mod),mod));//費(fèi)馬小定理
}
}
