拓展欧几里
拓展欧几里得：求直线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）的整倍数时无整数解