线性同余和扩展欧几里得的运用小结

内容回顾：

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
ax≡b (mod n)的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。这时，如果 x0 是方程的一个解，那么所有的解可以表示为：
{x0+kn/d|(k∈z)}
其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。

扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

在我具体的做题过程中遇到了一些中国剩余定理的题目，基本上也都是可以用扩展欧几里德算法解决的，而在求解线性同余方程组时，一般用扩展欧几里德解决，而且我习惯只写一个扩展欧几里德调用函数，因为它也可以求得gcd，根本就不需要再用一个欧几里德算法求最大公约数。

中国剩余定理也有一些整理：传送阵

例题：

POJ1061 青蛙的约会

这是一道最简单的线性同余题目，题意中文（目测也没什么外国人看我blog）就不多说了，，，一个扩展欧几里德搞定。。。不过，青蛙的约会确实戳中泪点了，码农的爱情~

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<set>#include<vector>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i<b;++i)#define N 1000000007using namespace std;inline void RD(int &ret){    char c;    do    {        c=getchar();    }    while(c<'0'||c>'9');    ret=c-'0';    while((c=getchar())>='0'&&c<='9')    {        ret=ret*10+(c-'0');    }}inline void OT(int a){    if(a>=10)    {        OT(a/10);    }    putchar(a%10+'0');}__int64 exdgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){    __int64 l,r;    if(b==0)    {        x=1;        y=0;        return a;    }    r=exdgcd(b,a%b,x,y);    l=x;    x=y;    y=l-a/b*y;    return r;}int main(){    __int64 a,b,c,x1,x2,y1,y2,p,sum,x,y,x0,y0,lx,ly,rx,ry,l,r;    scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&x1,&x2,&y1,&y2);    if(a==0&&b==0)    {        if(c==0)        {            sum=(x2-x1+1)*(y2-y1+1);        }        else        {            sum=0;        }    }    else if(a==0)    {        if((-c)%b==0)        {            y0=(-c)/b;            if(y0>=y1&&y0<=y2)            {                sum=(x2-x1+1);            }            else            {                sum=0;            }        }        else        {            sum=0;        }    }    else if(b==0)    {        if((-c)%a==0)        {            x0=(-c)/a;            if(x0>=x1&&x0<=x2)            {                sum=(y2-y1+1);            }            else            {                sum=0;            }        }        else        {            sum=0;        }    }    else    {        p=exdgcd(a,b,x,y);        if((-c)%p!=0)        {            sum=0;        }        else        {            x=(x*(-c))/p;            y=(y*(-c))/p;            lx=(x1<=x||(x1-x)*p%b==0)?((x1-x)*p/b):((x1-x)*p/b+1);            rx=(x2>=x||(x2-x)*p%b==0)?((x2-x)*p/b):((x2-x)*p/b-1);            ly=(y1<=y||(y-y1)*p%a==0)?((y-y1)*p/a):((y-y1)*p/a-1);            ry=(y2>=y||(y-y2)*p%a==0)?((y-y2)*p/a):((y-y2)*p/a+1);            if(lx>rx)            {                swap(lx,rx);            }            if(ly>ry)            {                swap(ly,ry);            }            if(ry>=lx&&rx>=ly)            {                l=max(lx,ly);                r=min(rx,ry);                sum=r-l+1;            }            else            {                sum=0;            }        }    }    printf("%I64d\n",sum);    return 0;}

最后附上Matrix67神的线性同余和扩展欧几里德解析，很有意思：mod&&exdgcd