Редакция для Лампы вдоль провода

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Автор: montes332

Разбор задачи «Лампы вдоль провода»

1. Идея

Нужно посчитать количество точек с целочисленными координатами на отрезке между двумя целочисленными точками A(x1, y1) и B(x2, y2).

Ключевой факт этой задачи:

Если dx = |x2 - x1|, dy = |y2 - y1|, то количество целочисленных точек на отрезке равно gcd(dx, dy) + 1, где gcd — наибольший общий делитель.

Значит, задача сводится к вычислению НОД двух чисел.

2. Наблюдения

Рассмотрим вектор от точки A к точке B:

по x он изменяется на x2 - x1
по y он изменяется на y2 - y1

Пусть:

dx = |x2 - x1|
dy = |y2 - y1|

Наблюдение 1

Если отрезок горизонтальный, например от (0, 0) до (5, 0), то целочисленные точки очевидны:

(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0)
(5, 0)

Их 6, то есть 5 + 1. Здесь gcd(5, 0) = 5.

Наблюдение 2

Если отрезок идет по диагонали, например от (0, 0) до (2, 2), то целочисленные точки:

(0, 0)
(1, 1)
(2, 2)

Их 3, а gcd(2, 2) = 2, снова получаем 2 + 1 = 3.

Наблюдение 3

Если взять отрезок от (0, 0) до (6, 4), то:

dx = 6
dy = 4
gcd(6, 4) = 2

Значит, на отрезке будет 2 + 1 = 3 целочисленные точки:

(0, 0)
(3, 2)
(6, 4)

Почему шаг именно (3, 2)? Потому что это вектор (6, 4), делённый на 2.

Главное наблюдение

Если g = gcd(dx, dy), то вектор (x2 - x1, y2 - y1) можно разбить на g одинаковых шагов:

по x: (x2 - x1) / g
по y: (y2 - y1) / g

Этот шаг уже нельзя сократить, то есть между соседними такими точками других целочисленных точек нет.

Значит, всего точек будет:

начало отрезка
потом ещё g шагов

Итого g + 1.

3. Алгоритм

Считать x1, y1.
Считать x2, y2.
Вычислить:
- dx = abs(x2 - x1)
- dy = abs(y2 - y1)
Найти g = gcd(dx, dy) алгоритмом Евклида.
Вывести g + 1.

4. Почему это работает

Рассмотрим все целочисленные точки на отрезке от A до B.

Пусть:

dx = x2 - x1
dy = y2 - y1
g = gcd(|dx|, |dy|)

Тогда можно записать:

dx = g * px
dy = g * py

где числа px и py взаимно просты.

Тогда все точки вида

(x1 + k * px, y1 + k * py)

для k от 0 до g будут целочисленными и лежат на отрезке.

Почему других целочисленных точек нет?

Потому что шаг (px, py) уже несократим: у px и py нет общего делителя больше 1. Значит, между двумя соседними такими точками нельзя вставить ещё одну точку с целыми координатами на той же прямой.

Следовательно, целочисленные точки на отрезке — это ровно точки с номерами k = 0, 1, 2, ..., g.

Их количество равно g + 1.

5. Сложность

Алгоритм Евклида работает за O(log(min(dx, dy))).

Итоговая сложность:

по времени: O(log(max(dx, dy)))
по памяти: O(1)

6. Код на C++17

#include <iostream>
#include <cstdlib>

using namespace std;

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1;
    cin >> x2 >> y2;

    long long dx = llabs(x2 - x1);
    long long dy = llabs(y2 - y1);

    long long g = gcd_ll(dx, dy);
    cout << g + 1 << '\n';

    return 0;
}

7. Код на Python 3

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())

dx = abs(x2 - x1)
dy = abs(y2 - y1)

while dy != 0:
    dx, dy = dy, dx % dy

print(dx + 1)