写这个模板的直接原因也是最近在扩展欧几里德上吃了大亏。。
欧几里德算法：
即利用辗转相除法计算a与b的最大公因数gcd
int gcd(int a,int b)
{
if(!b) return a;
else return gcd(b,a%b);
}
扩展欧几里德算法：
对于同余方程ax=c(mod b)求整数解
即对线性方程ax-by=c求x,y的整数解
我们讨论更一般的情况：
ax+by=c的整数解
扩展欧几里德算法能够求出 ax+by=gcd(a,b) 这样一个方程组x,y和的绝对值的一组整数解，代码如下：
int exgcd(int a,int b,int& x,int& y)
{
if(!b)
{
x=1;y=0;
return a;
}
else
int res=exgcd(b,a%b,y,x);
y-=x*(a/b);
return res;
}
若gcd(a,b)整除c，那么只要将ax+by=gcd(a,b)的解(x,y)乘上c/gcd(a,b)，就可以得到方程的一组特解：
x0=x*c/gcd(a,b)
y0=y*c/gcd(a,b)
若gcd(a,b)不能整除c，那么方程组就不存在整数解。
那么在方程组有解的情况下，每一个解都能够用它的一组特解来表示：
x=x0 + b / gcd(a,b) * t
y=y0 - a / gcd(a,b) * t
其中t= 0，1，-1，2，-2，3，-3...证明也非常简单。
那么最常见的两个问题是求最小的非负x，或者求最小的非负(x,y)
对于第一个问题，最小的非负x可以由x0不停地加上b/(a,b)得到
对于第二个问题，最小的非负(x,y)不一定存在，我们需要分情况讨论。
当a<0且b<0时，相当于a>0且b>0时求最大负数解
当a和b中只有一个小于零的时候，非负解一定存在，将(x0,y0)不停地加上(b,a)的绝对值即可
当a和b都大于0时，若x<0，则将x不停加b，y不停减a，若x>0的时候y<0则没有非负解。若x>0时y>0，则根据a和b的大小关系继续加减，确保(x,y)是绝对值和最小的一组非负整数解。
代码如下：
//求最小非负的x
int exgcd_x(int a,int b,int& x,int& y)
{
int d=exgcd(a,b,x,y);
if(x<0)
{
b/=d;b>0?b:-b;
int t=x%b?-x/b:-x/b+1;
x+=b*t;
}
return x;
}
昨天写了求(x,y)的最小非负整数解算法，但是仔细想想发现有问题。
当求ax+by=c的时候，会先求ax+by=gcd(a,b)的一组特解，然后将其乘上c/gcd(a,b)，即x*=c/gcd(a,b)。这个时候产生了一个很重要的问题，那就是如果c的范围是10^18，也就是说接近long long的最大范围，那么x*c/gcd(a,b)就有可能爆long long，所以说其实(x,y)的最小非负整数解还是有些细节需要处理的。于是决定根据针对昨天遇到的那道题目来写。
//求ax+by=c是否有非负整数解，保证a,b,c > 0。 a,b<10^9 , c<10^18
bool exexgcd(long long a,long long b,long long c)
{
long long x,y;
long long d=exgcd(a,b,x,y);//求扩欧
if(c%d) return false;//无解
if(x>=0 && y>=0) return true;
if(y<0)//保证x是小于0的那个
{
int temp=a;
a=b;b=temp;
temp=x;
x=y;y=temp;
}
a/=d;b/=d;c/=d;
//先将x尽量加到接近0
long long t=-x/b;
y-=a*t;
x+=b*t;
if(y<0) return false;
if(x==0) return true;
x=-x;//让x取绝对值
long long right=(y*(c%a)/a)+y*(c/a);
//表示y在乘上c之后最多能够减多少次a还大于等于0.为了防止爆long long，将c拆开处理了
long long left=x*(c%b);
if(left%b) left=left/b+1;
else left=left/b;
left=left-right+x*(c/b);
//表示x需要加多少次。同样，为了防止爆long long，不仅把c拆开处理而且还先减去了y能够减的次数right
//如果x需要加的次数小于等于y能够减的次数，返回true
if(left<=0) return true;
else return false;
}