В прямоугольнике с целыми сторонами m и n, нарисованном на клетчатой бумаге, проведена диагональ. Через какое число узлов она проходит? На сколько частей эта диагональ делится линиями сетки?
Число узлов = НОД( m, n ) + 1 число частей = m + n - НОД( m, n )
(m, n) + 1 число узлов она проходит m + n - (m, n) частей диагональ делится линиями сетки