扩展欧几里得算法

——by《紫书》

---

问题引入：

直线上的点。求直线ax+by+c=0上有多少个整点(x,y)满足x∈[x1,x2]，y∈[y1,y2]。

---

分析：

这里先介绍本问题核心的算法——扩展欧几里得算法。

扩展欧几里得算法： 找出一对整数(x,y)，使得ax+by=gcd(a,b)。这里的x和y不一定是整数，也可能是0或负数。 ax+by = gcd(a,b)这个式子总是有解。 void gcd(int a, int b, int &d, int &x, int &y) { if(!b){ d = a; x = 1; y = 0;//gcd(a,0)=1*a-0*0=a }else{ gcd(b, a%b, d, y, x); y -= x*(a/b); } }

x和y就是ax+by = gcd(a,b)的其中一个解，d是gcd(a,b)。

现在求的只是一个解，那么还有其他解吗？当然，还有无数个！ 设a,b,c为任意整数。若方程ax+by=c的一组整数解为(x0,y0)，则它的任意整数解都可以写成(x0+kb’ , y0-ka’)，其中a’= a/gcd(a,b) , b’= b/gcd(a,b)，k为任意整数。

那么原问题就可以通过扩展欧几里得算法解决了。 原问题是求ax+by+c=0的解。移项得ax+by = -c。那么如果c是gcd(a,b)的倍数，那么就一定有解。 即 设a,b,c为任意整数，g = gcd(a,b)，方程ax+by=g的一组解是(x0,y0)，则当c是g的倍数时，ax+by=c的一组解是(x0c/g , y0c/g)；当c不是g的倍数时无整数解。

代码如下：

#include<cstdio> using namespace std; const int INF = 1000; void gcd(int a, int b, int &d, int &x, int &y) { if(!b) { d = a; x = 1; y = 0; }else{ gcd(b, a%b, d, y, x); y -= x*(a/b); } } int main() { int a,b,c,d; scanf("%d%d%d",&a,&b,&c); int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&x2,&y1,&y2);//整点的范围 int x0,y0; //ax+by=gcd(a,b)的一个解 gcd(a,b,d,x0,y0); int a2 = a/d, b2 = b/d; //其他解 int count = 0; if(c%d==0) { for(int k=0; k<INF; k++) { x0 = x0+k*b2; y0 = y0-k*a2; if(x0<x1||x0>x2||y0<y1||y0>y2) continue; count++; } } printf("%d\n",count); return 0; }