欧几里得，扩展欧几里得相关

欧几里得（gcd）

欧几里得算法通过辗转相除法求得x，y的最小公约数

/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd(int n, int m)
{
    while(m>0)//余数大于零
    {
        int c = n % m;
        n = m;
        m = c;
    }
    return n;//输出最后一个整除的数
}

扩展欧几里得

扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数–这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

long long exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0) { x=1,y=0; return a; }
long long d=exgcd(b,a%b,x,y);
long long tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}

通过扩展欧几里得求逆元

(A*X)%MOD=1；那么肯定存在k使得

A*X=k*MOD+1；

移项可得：A*X-k*MOD=1;

所以，当A和MOD互素时，就可以写成

A*X-k*MOD=gcd(A,MOD)；

如果把A看做a，MOD看做b，X看做x，-k看做y的话，则上式可化为：

ax+by=gcd(a,b)；

这样就可以用扩展欧几里得算法求出来x了，也就是我们要找的逆元。

int mod_reverse(int a,int n)//ax=1(mod n) 求a的逆元x 
{
    int d,x,y;
    d=ex_gcd(a,n,x,y);
    if(d==1)
        return (x%n+n)%n;
    else
        return -1;
}