欧几里得算法：
递归版本：
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 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 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);
根据朴素的欧几里德原理有 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;
根据恒等定理得：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）使用扩展欧几里德算法解决不定方程的办法：
对于不定整数方程a*x+b*y=c，若 c mod Gcd(x, y)=0,则该方程存在整数解，否则不存在整数解。 上面已经列出找一个整数解的方法，在找到 a*x+ b*y = Gcd(a,b)的一组解x0,y0后，
a*x+b*y = Gcd(a, b)的其他整数解满足：
x = x0 + b/Gcd(a, b) * t
y = y0 - a/Gcd(a, b) * t(其中t为任意整数)
因为a*x+b*y=a(x0 + b/Gcd(a, b) * t)+b(y0 - a/Gcd(a, b) * t)=Gcd(a,b)
其中，最小的正整数x为: x=x0%( b/Gcd(a, b) )
最小的正整数y: y=y0%( a/Gcd(a, b) )
至于ax+by=c的整数解，只需将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为任意整数
*/
return true;
}
(2)用扩展欧几里德算法求解模线性方程的方法：
同余方程 ax≡b (mod n),即（a*x-b) mod n=0;推出a*x+n*y=b;所以转化为求不定方程a*x+n*y=Gcd(a,n)。
如果b%(Gcd(a,n))!=0,那么方程无整数解;否则求出初解x0,然而初值还要乘以b/Gcd(a,n),即x=x0*b/Gcd(a,n)才是方程a*x+n*y=b的解
而其他整数解则满足：
x(i) = x + b/Gcd(a, b) * t
y(i) = y - a/Gcd(a, b) * t (其中t为任意整数)
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互质），则称a关于模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为素数)，稍作变形即是 a*a^(p-2)≡ 1(mod p)，是不是发现了，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关于对mod取模的逆元为pow_mod(b,mod-2,mod);
题目：求(a/b)%mod。
题解：先求出b的逆元，然后结果为(a*(b^-1) )%mod，b^-1指b关于对mod取模运算的逆元
#include<stdio.h>
#include <string.h>
using namespace std;
const long long mod=9973;//一个素数
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));//费马小定理
}
}
