Question

Сколько клеток пересекает диагональ в клетчатом прямоугольнике размерами 199 на 991?

Answer 1

НОД (199, 991) = НОД (195, 199) = НОД (4, 195) = НОД (1, 4) = 1. Поэтому на диагонали нет узлов сетки и она пересекает 991+199-1=1189 клеток.

Answer 2

Числа 199 и 991 взаимно простые, потому что не имеют общих делителей, кроме единицы.
Это значит, что диагональ такого прямоугольника не проходит через "пересечения клеточек" нигде, кроме своего начала и конца.
Отсюда следует, что вертикальных пар клеток, которые пересечет диагональ будет на одну меньше, чем количество клеток по длине прямоугольника.
Итак: 199 + 991 - 1 = 1189 клеток
Ответ: диагональ прямоугольника пересекает 1189 клеток.