Через сколько клеток проходит отрезок?

Question

[dmitrii2004]

Отрезок
На клетчатой бумаге нарисовали отрезок, соединяющий точки с координатами (a,b) и (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через её внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку)?

Входные данные

Программа получает на вход четыре целых числа, записанных в одной строке: a,b,c,d. Все числа по модулю не превосходят 106.

Выходные данные

Выведите ответ на задачу.
Примеры
Ввод
0 0 6 4
Вывод
8
Помогите пожалуйста сайт при выполнении программы пишет неверный ответ

#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

[Wataru]

Проблема в том, что GCD(0,1000) = 1000. А у вас цикл ни разу не выполнится и не найдет ничего.

Ваше решение не работет, если отрезок вертикальный или горизонтальный. Ответ должен быть 0, вы же выведите что-то другое.

Но, когда вы это исправите, ваше решение скорее всего не пройдет по времени. Ищите наибольший общий делитель алгоритмом евклида.

Answer 2

[Sergey]

Находишь наибольший общий делитель dX и dY и вычитаешь его из суммы dX и dY

6 + 4 - 2 = 8

Comments

[NightCAT_Busya]

Напиши, пожалуйста, как ты дошел до этого. Очень хотелось бы понять. Буду бесконечно благодарна