Блог пользователя lilPanda

Как доказать следующее?
Автор lilPanda, 9 лет назад, По-русски

Даны две точки p1 = (x1,y1) и p2 = (x2,y2). Надо найти кол-во точек с целочисленными координатами на отрезке p1p2. Ну, ясен пень, что кол-во таких точек будет gcd(|x2-x1|,|y2-y1|) + 1(добавили еще начальную точку). Но как мне доказать, что это на самом деле так? З.Ы. Примерный вопрос был, но док-ва там не было.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

ну рассмотрим отрезок, у которого вертикальная составляющая h = |y1 - y2|, а горизонтальная w = |x2 - x1|. Все точки на этом отрезке имеют координаты . Сразу видно, что нас интересуют только рациональные k, то есть, . Из того, что и делаем вывод, что либо мы можем сразу привести дробь к такому виду, что , либо p и q не взаимно просты и мы сможем привести дробь к такому виду после их сокращения.

Таким образом, нас интересует множество k, в котором знаменатель — это , а числитель — целое неотрицательное число p ≤ q. Таких дробей, очевидно,

→ Ответить