使用扩展欧几里德算法来查找线段与二维网格上的点的交点数

Question

在由网格点（M * x，M * y）构造的网格中给出点A（x1，y1）和点B（x2，y2）其中所有变量都是整数。我需要检查从点A到点B的线段上有多少个网格点。我知道可以通过使用扩展的欧几里得算法来完成，但我不知道如何去做。我很感谢你的帮助。

Answer 1

改写，要确定有多少数量t满足

(1) M divides (1-t) x1 + t x2 
(2) M divides (1-t) y1 + t y2 
(3) 0 <= t <= 1. 

让我们专注于(1)。我们引入变量q代表整除约束和解决的整数。t：

exists integer q, M q = (1-t) x1 + t x2 

exists integer q, M q - x1 = (x2 - x1) t. 

如果x1不等于x2，则这给出了一个周期性的组的形式t in {a + b q | q integer}，其中a和b是馏分的可能性。否则，所有t或没有t都是解决方案。

扩展欧几里得算法对于交叉(1)和(2)产生的解集有用。假设我们要计算交会

{a + b q | q integer} intersect {c + d s | s integer}. 

通过表达两种不同方式的一般常见的元素，我们来到了linear Diophantine equation：

a + b q = c + d s, 

其中a, b, c, d是恒定的，q, s是整数。让我们清楚的分母和收集方面为一体式

A q + B s = C, 

其中A, B, C是整数。当且仅当A和B的最大公约数g也分为C时，该等式才有解。使用扩展欧几里德算法计算整数系数u, v这样

A u + B v = g. 

然后，我们对每个整数k解决

q = u (C/g) + k (B/g) 
s = v (C/g) - k (A/g) 

。

最后，我们必须考虑约束(3)。这应该归结为一些算术和一个楼层的划分，但我不想详细说明（到目前为止我写的特殊情况已经需要很多时间）。

Answer 2

让我们dX = Abs(x2-x1)和dY = Abs(y2 - y1)
然后在段格点的数量是

P = GCD(dX, dY) + 1 

（包括起点和终点）
其中GCD是最大公约数（通过平时（不扩展）欧几里德算法）

（见最后属性here）

Answer 3

继David Eisenstat先生的指示我已经设法用C++编写了一个计算答案的程序。

#include <iostream> 
#include <math.h> 

using namespace std; 

int gcd (int A, int B, int &u, int &v) 
{ 
int Ad = 1; 
int Bd = 1; 
if (A < 0) { Ad = -1; A = -A; } 
if (B < 0) { Bd = -1; B = -B; } 

int x = 1, y = 0; 
u = 0, v = 1; 

while (A != 0) 
{ 
    int q = B/A; 
    int r = B%A; 
    int m = u-x*q; 
    int n = v-y*q; 
    B = A; 
    A = r; 
    u = x; 
    v = y; 
    x = m; 
    y = n; 
} 

u *= Ad; 
v *= Bd; 

return B; 
} 

int main(int argc, const char * argv[]) 
{ 
int t; 
scanf("%d", &t); 

for (int i = 0; i<t; i++) { 

    int x1, x2, y1, y2, M; 

    scanf("%d %d %d %d %d", &M, &x1, &y1, &x2, &y2); 

    if (x1 == x2) // vertical line 
    { 
     if (x1%M != 0) { // in between the horizontal lines 
      cout << 0 << endl; 
     } else 
     { 
      int r = abs((y2-y1)/M); // number of points 
      if (y2%M == 0 || y1%M == 0) // +1 if the line starts or ends on the point 
       r++; 

      cout << r << endl; 
     } 

    } else { 

     if (x2 < x1) 
     { 
      int c; 
      c = x1; 
      x1 = x2; 
      x2 = c; 
     } 

     int A, B, C; 

     C = x1*y2-y1*x2; 
     A = M*(y2-y1); 
     B = -M*(x2-x1); 

     int u, v; 
     int g = gcd(A, B, u, v); 

     //cout << "A: " << A << " B: " << B << " C: " << C << endl; 
     //cout << A << "*" << u <<"+"<< B <<"*"<<v<<"="<<g<<endl; 

     double a = -x1/(double)(x2-x1); 
     double b = M/(double)(x2-x1); 

     double Z = (-a-C*b/g*u)*g/(B*b); 
     double Y = (1-a-C*b/g*u)*g/(B*b); 

     cout << floor(Z) - ceil(Y) + 1 << endl; 
    } 
} 
return 0; 
} 

谢谢你的帮忙！请检查是否考虑到所有特殊情况。