Разбор задачи «Точки на координатной сетке»

Нужно посчитать количество целочисленных точек (x, y), которые:

• лежат в прямоугольнике x1 <= x <= x2, y1 <= y <= y2;
• удовлетворяют уравнению a * x + b * y = c.

Ограничения большие, поэтому перебирать точки прямоугольника нельзя.

1. Идея

Нужно не искать точки по одной, а описать сразу все целочисленные решения уравнения

a * x + b * y = c.

Для этого используется расширенный алгоритм Евклида:

• он находит g = gcd(a, b);
• вместе с этим даёт такие xg и yg, что

a * xg + b * yg = g.

Если c не делится на g, то решений вообще нет.

Если делится, то можно получить одно решение (x0, y0) уравнения a * x + b * y = c, а дальше записать все решения через один параметр t.

После этого останется понять, при каких t точка попадает в прямоугольник. Это сведётся к пересечению двух отрезков по t.

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

Наблюдение 1. Когда решения существуют

Уравнение

a * x + b * y = c

имеет целочисленные решения тогда и только тогда, когда c делится на gcd(a, b).

Это стандартный факт про линейные диофантовы уравнения.

Наблюдение 2. Как получить одно решение

Если расширенный алгоритм Евклида нашёл числа xg, yg такие, что

a * xg + b * yg = g,

то после умножения на c / g получаем

a * (xg * c / g) + b * (yg * c / g) = c.

Значит, одно решение:

• x0 = xg * (c / g)
• y0 = yg * (c / g)

Наблюдение 3. Как выглядят все решения

Если (x0, y0) — одно решение, то все решения имеют вид:

• x = x0 + (b / g) * t
• y = y0 - (a / g) * t

где t — любое целое число.

Обозначим:

• dx = b / g
• dy = a / g

Тогда:

• x = x0 + dx * t
• y = y0 - dy * t

Наблюдение 4. Ограничения на t

Нужно, чтобы одновременно выполнялось:

• x1 <= x0 + dx * t <= x2
• y1 <= y0 - dy * t <= y2

Из первого получаем допустимый отрезок для t по координате x.

Из второго — допустимый отрезок для t по координате y.

Ответ — количество целых t в пересечении этих двух отрезков.

3. Алгоритм

1. Считываем a, b, c и границы прямоугольника x1, x2, y1, y2.
2. С помощью расширенного алгоритма Евклида находим:
   • g = gcd(a, b)
   • xg, yg, для которых a * xg + b * yg = g.
3. Если c % g != 0, выводим 0.
4. Иначе строим одно решение:
   • mult = c / g
   • x0 = xg * mult
   • y0 = yg * mult
5. Находим шаги общего решения:
   • dx = b / g
   • dy = a / g
6. Находим допустимый диапазон t из условия на x:
   • x1 <= x0 + dx * t <= x2
   • значит
     • lx = ceil((x1 - x0) / dx)
     • rx = floor((x2 - x0) / dx)
7. Находим допустимый диапазон t из условия на y:
   • y1 <= y0 - dy * t <= y2
   • это равносильно
     • y0 - y2 <= dy * t <= y0 - y1
   • значит
     • ly = ceil((y0 - y2) / dy)
     • ry = floor((y0 - y1) / dy)
8. Пересекаем диапазоны:
   • l = max(lx, ly)
   • r = min(rx, ry)
9. Если l > r, ответ 0, иначе ответ r - l + 1.

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

Расширенный алгоритм Евклида даёт коэффициенты, из которых строится одно решение уравнения a * x + b * y = c, если такое решение существует.

Далее используется классический факт: все решения линейного диофантова уравнения образуют семейство, зависящее от одного целого параметра t:

• x = x0 + (b / g) * t
• y = y0 - (a / g) * t

Поэтому задача сводится к тому, чтобы найти все такие целые t, для которых точка попадает в прямоугольник.

Условие на x задаёт некоторый целочисленный интервал по t. Условие на y задаёт ещё один интервал по t.

Подходящие точки существуют ровно для тех t, которые лежат в пересечении этих интервалов. Каждому такому t соответствует ровно одна точка (x, y), и наоборот, каждая подходящая точка соответствует ровно одному t.

Значит, количество точек равно количеству целых чисел в пересечении интервалов.

5. Сложность

Расширенный алгоритм Евклида работает за O(log min(a, b)).

Все остальные действия выполняются за O(1).

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

• по времени: O(log min(a, b))
• по памяти: O(log min(a, b)) из-за рекурсии в расширенном алгоритме Евклида

6. Код на C++17

#include <iostream>
#include <algorithm>

using namespace std;

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long floor_div(long long a, long long b) {
    if (a >= 0) return a / b;
    return -((-a + b - 1) / b);
}

long long ceil_div(long long a, long long b) {
    if (a >= 0) return (a + b - 1) / b;
    return -((-a) / b);
}

int main() {
    long long a, b, c;
    long long x1, x2, y1, y2;

    cin >> a >> b >> c;
    cin >> x1 >> x2 >> y1 >> y2;

    long long xg, yg;
    long long g = extgcd(a, b, xg, yg);

    if (c % g != 0) {
        cout << 0 << '\n';
        return 0;
    }

    long long mult = c / g;
    long long x0 = xg * mult;
    long long y0 = yg * mult;

    long long dx = b / g;
    long long dy = a / g;

    long long lx = ceil_div(x1 - x0, dx);
    long long rx = floor_div(x2 - x0, dx);

    long long ly = ceil_div(y0 - y2, dy);
    long long ry = floor_div(y0 - y1, dy);

    long long l = max(lx, ly);
    long long r = min(rx, ry);

    if (l > r) {
        cout << 0 << '\n';
    } else {
        cout << (r - l + 1) << '\n';
    }

    return 0;
}

7. Код на Python 3

def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

def floor_div(a, b):
    return a // b

def ceil_div(a, b):
    return -((-a) // b)

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

g, xg, yg = extgcd(a, b)

if c % g != 0:
    print(0)
else:
    mult = c // g
    x0 = xg * mult
    y0 = yg * mult

    dx = b // g
    dy = a // g

    lx = ceil_div(x1 - x0, dx)
    rx = floor_div(x2 - x0, dx)

    ly = ceil_div(y0 - y2, dy)
    ry = floor_div(y0 - y1, dy)

    l = max(lx, ly)
    r = min(rx, ry)

    if l > r:
        print(0)
    else:
        print(r - l + 1)