使用擴展歐幾里德算法來查找線段與二維網格上的點的交點數

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; 
} 

謝謝你的幫忙！請檢查是否考慮到所有特殊情況。