拓展欧几里

拓展欧几里得：求直线ax+by+c=0上有多少个整数点（x,y）满足x1<x<x2,y1<y<y2.

exgcd代码

void exgcd(int a,int b,int &d,int &x,int &y)
{
    if(!b)
    {
        d=a;//gcd(a,b) 
        x=1;
        y=0;
    }
    else
    {
        exgcd(b,a%b,d,y,x);//注意交换x,y 
        y-=x*(a/b);
    }
}

通过exgcd求出一直特解（x0,y0）

则任意整数解都可以写成（x0+kb',y0-ka'）k取任意整数

若c不是gcd（a,b）的整倍数时无整数解