Задача на диофант

Информатика
1

Помогите с задачей F. Я понял что задача сводиться к тому, что надо найти общее время где оба гонщика будут в середине. Но непонятно как найти это время.

1 лайк
2

Они столкнутся если существует такое t что выполняется:
V_1 * t * \mod L_1 = 0
V_2 * t * \mod L_2 = 0
V_1 * t = x * L_1, x \in N
V_2 * t = y * L_2, y \in N
t = x * \frac{L_1}{V_1}
t = y * \frac{L_2}{V_2}
co_1 = \frac{L_1}{V_1}, co_2 = \frac{L_2}{V_2}

co_1 * x = co_2 * y
co_1 * x - co_2 * y = 0

Это обычная диофаната, тебе нужно проверить существует ли пара натуральных {x, y} которая является решением этого уравнения. Коэффициенты нецелые? Ну умножь оба коэфа на НОК(V_1, V_2), там всё равно справа 0

1 лайк
3

Разве не надо учитывать еще и L2 / V1 и L1/V2. Тип они же восьмеркой едут.

1 лайк
4

Я даун… я думал они едут по кругам своим, сейчас исправлю

5

L = L_1 + L_2

Столкновения происходят в двух случаях:

  1. V_1 * t \mod L = 0 и V_2 * t \mod L = L_2
  2. V_1 * t \mod L = L_1 и V_2 * t \mod L = 0

Случаи можно решить раздельно :

  1. \displaystyle V_1 * t = L * x,\quad x \in N\qquad\Rightarrow\qquad t = \frac{L}{V_1} * x,\quad x \in N
    \displaystyle V_2 * t = L * y + L_2,\quad y \in N\qquad\Rightarrow\qquad t = \frac{L}{V_2} * y + \frac{L_2}{V_2},\quad y \in N
    \displaystyle\frac{L}{V_1} * x = \frac{L}{V_2} * y + \frac{L_2}{V_2},\quad y \in N,\quad x \in N
    \displaystyle\frac{L}{V_1} * x - \frac{L}{V_2} * y = \frac{L_2}{V_2},\quad y \in N,\quad x \in N\quad Домножим обе части на \text{lcm}({V_1}, {V_2})
    \displaystyle c_1 = \frac{L * \text{lcm}({V_1}, {V_2})}{V_1},\quad c_2 = \frac{L * \text{lcm}({V_1}, {V_2})}{V_2},\quad c_3 =\frac{L_2\text{lcm}({V_1}, {V_2})}{V_2}
    c_1*x - c_2*y = c_3
    Тут если есть хотя бы одно целое решение то значит и натуральное есть, так как
    x = x_0 + c_2 * k,\quad y = y_0 + c_1 * k,\quad k \in Z.
    В диофантах решение есть тогда когда выполняется c_3 \mod \text{gcd}(c_1, c_2) = 0, иначе решений нету.
    Почему? Потому что мы можем вынести общий множитель часть слева и перенести его направо, если оно не делится то значит что число справа нецелое, а слева всегда целое, тк коэфы целые и переменные целые. Всё.

  2. Аналогично разбираем.

3 лайка
6

Непонятна часть с тем что если есть целые решения то есть натуральные. И x, y находят расширенным евклидом?

7

А стоп. Тут же не надо коэффициенты находить…

1 лайк