求最大公约数

原理：gcd(a,b)=gcd(b,a mod b)

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：

⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则

gcd(a,b) = gcd(b,r)

⒉ a 和其倍数之最大公因子为 a。

另一种写法是：

⒈ 令r为a/b所得余数（0≤r<b）

若 r= 0，算法结束；b 即为答案。

⒉ 互换：置 a←b，b←r，并返回第一步。

欧几里德算法的C语言实现：

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

递归写法：

int gcd(int a,int b)
{
    if(a<b){int temp;temp=a;a=b;b=temp;} 
    if(b==0)return a;
    return gcd(b,a%b);
}

最小公倍数 = a*b/最大公约数 注意超过范围32位

用a*(b/最大公约数）就不会超过32位了 而且有时需用到long long

扩展欧几里得算法

求ax+by=gcd(a,b)（这里a和b都是正整数所以解释了后面带入的为什么是m,n）

int extgcd(int a,int b,int &x,int &y)
{
    int d=a;
    if(b!=0){
        d=extgcd(b,a%b,y,x);
        y=y-(a/b)*x;
    }
    else{
        x=1;y=0;
    }
    return d;
} 
int main()
{
    int x,y;
    extgcd(4,11,x,y);
    printf("%d %d\n",x,y);
    return 0;
}

扩展欧几里得算法的应用

（1）求解不定方程

用扩展欧几里得算法解不定方程ax+by=c;

这个应该比较好理解了，两个可以同乘以k.

（2）乘法逆元

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

思路：K M % N = 1等价于 KM=NX+1 即 KM+N*(-X)=1

根据扩展欧几里德算法，求出K和（-X）；

而K是应为正整数，即需要若K为负整数，则需要将之化正，即与负数取模同理，将K加上N，直至K>0为止，所得的数即为最小的乘法逆元；

若K为正整数，则直接输出即可。

int extgcd(int a,int b,int &x,int &y)
{
    int d=a;
    if(b!=0){
        d=extgcd(b,a%b,y,x);
        y=y-(a/b)*x;
    }
    else{
        x=1;y=0;
    }
    return d;
}
int main()
{
    int m,n,x,y;
    scanf("%d%d",&m,&n);
    extgcd(m,n,x,y);
    printf("%d\n",(x%n+n)%n);     //要使K最小，而且考虑K为负数的情况 
    return 0;
}

例如：4关于1模7的乘法逆元为多少？

4X≡1 mod 7

这个方程等价于求一个X和K，满足4X=7K+1,其中X和K都是整数。

若ax≡1 mod f, 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。

为什么要有乘法逆元呢？
当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。

用乘法逆元求组合数：

#define MOD 1000000007
long long extgcd(long long a,long long b,long long &x,long long &y)
{
    long long d=a;
    if(b!=0){
        d=extgcd(b,a%b,y,x);
        y=y-(a/b)*x;
    }
    else{
        x=1;y=0;
    }
    return d;
}
long long hx(long long a,long long b)
{
    long long x,y;
    extgcd(a,b,x,y);
    return (x%b+b)%b;
}
long long comb(long long n,long long m)
{
    long long fz=1,fm=1;
    int i;
    for(i=n;i>=m+1;i--)
    fz=(fz*i)%MOD;
    for(i=n-m;i>=2;i--)
    fm=(fm*i)%MOD;
    return (fz*hx(fm,MOD))%MOD;
}
int main()
{
    long long m,n;
    scanf("%lld%lld",&m,&n);
    printf("%lld\n",comb(m,n));
    return 0;
}

求解二元一次方程：

void extgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(!b){d=a;x=1;y=0;}
    else{extgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
    long long x,y,m,n,l,d,a,b,c;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=m-n;b=l;c=y-x;
    extgcd(a,b,d,x,y);
    if(c%d)printf("Impossible\n");
    else
    {
        x=x*(c/d);//c可以整除d
        b=b/d;
        if(b<0)b=-b;
        printf("%lld\n",(x%b+b)%b);
    }
    return 0;
}

求模线性方程组

以POJ 2891为例：

题意：给你k对a和r是否存在一个正整数x使每队a和r都满足：x mod a=r，求最小正解x或无解。

思路：

若模数两两互质，我们可以用中国剩余定理来解。
这里我们先考虑两个方程：

x≡r1(mod a1) x≡r2(mod a2)

我们可以写成:

x+y1a1=r1 x−y2a2=r2

相减得：

y1a1+y2a2=r1−r2

这就可以用扩展欧几里得解方程求出解：

设a, b, c为任意整数。若方程ax+by=c的一组整数解为(x0,y0)，则它的任意整数解都可以写成(x0+kb’,y0-ka’)，其中a’=a/gcd(a,b)，b’=b/gcd(a,b)，k取任意整数。

设a, b, c为任意整数，g=gcd(a,b)，方程ax+by=g的一组解是(x0,y0)，则当c是g的倍数时ax+by=c的一组解是(x0c/g,y0c/g)；当c不是g的倍数时无整数解。

若gcd(a,b)/|m那么方程就无解，直接输出-1。
否则我们可以解出上式的y1。回带得到一个特解x0=r1−y1a1。
通解可以写成x=x0+k∗lcm(a1,a2)也就是x≡x0(mod lcm(a1,a2))。
这样我们就将两个方程合并为了一个。重复进行以上操作，我们最终能将n个方程全部合并，再用扩展欧几德得解出来就好了。

long long a[100010],r[100010];
long long extgcd(long long a,long long b,long long &x,long long &y)
{
    long long d=a;
    if(b!=0){
        d=extgcd(b,a%b,y,x);
        y=y-(a/b)*x;
    }
    else{
        x=1;y=0;
    }
    return d;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lld%lld",&a[i],&r[i]);
        long long rr=r[0];
        long long aa=a[0];
        long long x,y,d;
        int sign=0;
        for(int i=1;i<n&&sign==0;i++)
        {
            d=extgcd(aa,a[i],x,y);
            //printf("%lld\n",x);
            if((rr-r[i])%d!=0)sign++;
            x=(rr-r[i])/d*x%a[i];//注意要模a[i]
            //printf("%lld\n",x);
            rr=rr-x*aa;
            aa=aa/d*a[i];//不能写成aa*a[i]/d会溢出
            rr=rr%aa;//这个rr可能很大，所以要模掉，模掉也没有影响
        }
        if(sign)printf("-1\n");
        else printf("%lld\n",(rr%aa+aa)%aa);
    }
    return 0;
}