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

Least common term of two arithmetic sequences
Автор Abhibansal53, история, 9 лет назад, По-английски

Given two arithmetic sequences (a1,d1 i.e. first term and common difference of first sequence and similarly a2,d2),what is the best algorithm to tell whether they have any common term,and if yes then tell the lowest one.

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

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

Let's say a[x]=b[y]. Then a1+d1*x=a2+d2*y or d1*x-d2*y=a2-a1. So, you just need to solve Diophantine equation.

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

I think this can be done with the Chinese Remainder Theorem. A term in both sequences is congruent to a1 (mod d1) and to a2 (mod d2), so you can find a number x such that any common term must be equal to x (mod lcm(d1, d2)) using Chinese Remainder Theorem (assuming there is at least one common term). Then, you can take the smallest value with that mod value that is greater than or equal to max(a1, a2).

→ Ответить