Through how many cells does the segment pass?

Question

Algorithms

Segment
On checkered paper, draw a line connecting the points with coordinates (a,b) and (c,d). How many cells does this segment pass through (it is considered that the segment passes through the cell if it passes through its interior, but if it passes only through the vertex or along the border of the cell, it is considered that it does not pass through the cell)?

Specifications Input

The program receives as input four integers written in one line: a,b,c,d. All modulo numbers do not exceed 106.

Output

Output the answer to the problem.
Examples
Input
0 0 6 4
Output
8
Please help the site writes the wrong answer when executing the program

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
int main()
{
   long long a, b, c, d, x, y, g = 1, x1, y1, k;
  cin >> a >> b >> c >> d;
  x = abs(a - c);
  y = abs(b - d);
  for (int i = 1; i <= min(x, y); i++)
  {
    if (x % i == 0 and y % i == 0)
    {
      g = i;
    }
  }
  x1 = x / g;
  y1 = y / g;
  k = x1 + y1 - 1;
  cout << g * k;

}

Answer 1

The problem is that GCD(0,1000) = 1000. And your loop will never be executed and will not find anything.
Your solution doesn't work if the segment is vertical or horizontal. The answer should be 0, but you should print something else.
But, when you fix it, your solution will most likely not pass in time. Search for the greatest common divisor by the Euclidean algorithm .

Answer 2

Find the greatest common divisor of dX and dY and subtract it from the sum of dX and dY

6 + 4 - 2 = 8