Надо чуть больше данных — от чего зависят прыжки? Чаще всего такая задача формулируется так: два кенгуру прыгают по числовой прямой по арифметическим прогрессиям x1(n) = s1 + n·a, n = 0,1,2,... x2(m) = s2 + m·b, m = 0,1,2,..., где s1,s2 — начальные точки, a и b — длины прыжков. Для этой формулировки ответ такой.
Общее правило
Обе прогрессии имеют общие точки тогда и только тогда, когда (s2 − s1) делится на g = gcd(a,b).Если делится, то наименьшая общая точка x0 находится решением сравнения a·n ≡ (s2 − s1) (mod b). После этого все общие точки задаются арифметической прогрессией x = x0 + k·L, k ∈ Z≥0, где L = lcm(a,b) = a·b/g.
Как найти x0 на практике
Вычислите g = gcd(a,b). Проверьте (s2 − s1) % g == 0. Если нет — общих точек нет.Пусть a' = a/g, b' = b/g, t = (s2 − s1)/g.Найдите обратный по модулю b' к a' (то есть число inv такое, что a'·inv ≡ 1 (mod b')).Тогда n0 ≡ t·inv (mod b'). Возьмите n0 в диапазоне 0..b'−1.x0 = s1 + n0·a. Тогда все общие точки x = x0 + k·L.
Пример s1 = 1, a = 4; s2 = 3, b = 6. g = gcd(4,6) = 2; s2−s1 = 2 делится на 2 ⇒ есть общие точки. L = lcm(4,6) = 12. Решаем 4·n ≡ 2 (mod 6) → делим на g: 2·n ≡ 1 (mod 3). Обратный к 2 по модулю 3 равен 2, значит n ≡ 2 (mod 3). n0 = 2 → x0 = 1 + 2·4 = 9. Все общие точки: 9, 21, 33, ...
Если дадите конкретные s1, a, s2, b — вычислю общие точки.
Надо чуть больше данных — от чего зависят прыжки? Чаще всего такая задача формулируется так: два кенгуру прыгают по числовой прямой по арифметическим прогрессиям
x1(n) = s1 + n·a, n = 0,1,2,...
x2(m) = s2 + m·b, m = 0,1,2,...,
где s1,s2 — начальные точки, a и b — длины прыжков. Для этой формулировки ответ такой.
Общее правило
Обе прогрессии имеют общие точки тогда и только тогда, когда (s2 − s1) делится на g = gcd(a,b).Если делится, то наименьшая общая точка x0 находится решением сравнения a·n ≡ (s2 − s1) (mod b). После этого все общие точки задаются арифметической прогрессиейx = x0 + k·L, k ∈ Z≥0,
где L = lcm(a,b) = a·b/g.
Как найти x0 на практике
Вычислите g = gcd(a,b). Проверьте (s2 − s1) % g == 0. Если нет — общих точек нет.Пусть a' = a/g, b' = b/g, t = (s2 − s1)/g.Найдите обратный по модулю b' к a' (то есть число inv такое, что a'·inv ≡ 1 (mod b')).Тогда n0 ≡ t·inv (mod b'). Возьмите n0 в диапазоне 0..b'−1.x0 = s1 + n0·a. Тогда все общие точки x = x0 + k·L.Пример
s1 = 1, a = 4; s2 = 3, b = 6.
g = gcd(4,6) = 2; s2−s1 = 2 делится на 2 ⇒ есть общие точки.
L = lcm(4,6) = 12.
Решаем 4·n ≡ 2 (mod 6) → делим на g: 2·n ≡ 1 (mod 3). Обратный к 2 по модулю 3 равен 2, значит n ≡ 2 (mod 3). n0 = 2 → x0 = 1 + 2·4 = 9.
Все общие точки: 9, 21, 33, ...
Если дадите конкретные s1, a, s2, b — вычислю общие точки.