12.1. Спільний елемент (подільність цілих чисел)
Зауваженя. З нескінченності арифметичних прогресій натуральних чисел випливає невід'ємність різниць цих прогресій.
Для двох прогресій {a + (k – 1) d} і {a' + (k – 1) d'} маємо таке:
Якщо d = d' = 0, то при a = a' єдиним спільним члено прогресій є a, інакше спільних членів немає.
Якщо d = 0 < d', то при цілому (a – a')/d' єдиним спільним членом прогресій є a, інакше спільних членів немає.
Якщо d' = 0 < d, то при цілому (a' – a)/d єдиним спільним членом прогресій є a', інакше спільних членів немає.
Якщо 0 < d і 0 < d', то прогресії мають спільний член тоді й лише тоді, коли (a – a') — різниця перших членів арифметичних прогресій — кратна НСД(d, d') — найбільшому спільному дільнику різниць цих прогресій. При цьому спільні члени обох прогресій утворюють арифметичну прогресію, різниця якої НСК(d, d') — найменше спільне кратне різниць цих прогресій. У цьому випадку пошук найменшого спільного члена двох арифметичних прогресій пов'язаний з пошуком найменших невід'ємних цілих k і k', що задовольняють таку рівність:
Такий пошук можна здійснити перебором: до різниці a – a' додавати числа kd, де k = 0, 1, 2, … доти, поки сума не стане кратною d'. Кількість таких додавань не перевищує d', бо всіх лишків від ділення на d' саме d': 0, 1, 2, ... , d' – 1.
Зі зроблених зауважень випливає: задачу можна розв'язувати, послідовно утворюючи нові арифметичні проґресії, члени яких є спільними членими перших j даних проґресій, j = 2, 3, …, n.
Подання числа масивом його цифр не потрібно робити у проміжних розрахунках, якщо скористатися такою властивістю остач від ділення на цілі числа: остача від ділення суми (добутку) залежить лише від суми (добутку) остач доданків (співмножників).
Нехай серед даних прогресій немає такої, різниця якої дорівнює 0. Позначимо:j
aj — перший член j-ої з даних арифметичних прогресій;
dj — різниця (між послідовними членами) j-ої з даних прогресій.
Різницю новоствореної арифметичної прогресії спільних членів перших j даних прогресій можна подати добутком чисел базового типу у вигляді:
Тут
с1 = d1;
с2 = НСК( d1 , d2 ) : d1;
с3 = НСК( d1 , d2 , d3 ) : НСК( d1 , d2 );
.....................................................................................
сj = НСК( d1 , d2 , … , dj ) : НСК( d1 , d2 , … , dj – 1 ).
Перший член цієї новоствореної прогресії можна подати арифметичним виразом такого вигляду:
де
0 ≤ k1 < d2 ,
0 ≤ k2 < d3 , …,
0 ≤ kj – 1 … dj.
12.2. Лабіринт (рекурентні співвідношення)
Зчитуючи символи вхідного файлу, створюємо прямокутну таблицю чисел розміру m × n, у якій елемент у i-му рядку j-го стовпчика дорівнює 0, 1 або 65535 (числу, що напевно перевищує mn), якщо j-ий символ (i + 1)-го рядка вхідного файлу відповідно є пропуском « », знаком додавання «+» чи іншим символом.
Умова задачі не фіксує m і n, тому цю таблицю зберігаємо у пам'яті ЕОМ у вигляді лінійного масиву.
Всі елементи таблиці, які є найближчими сусідами по вертикалі чи горизонталі числа 1 і дорівнюють 0, покладаємо рівними 2. Всі елементи таблиці, які є найближчими сусідами по вертикалі чи горизонталі числа 2 і дорівнюють 0, покладаємо рівними 3 і т.д. Всі елементи таблиці, які є найближчими сусідами по вертикалі чи горизонталі числа k і дорівнюють 0, покладаємо рівними k + 1 ... Елемент заповненої таким чином таблиці — збільшена на 1 найменша кількость кроків, яку потрібно зробити, щоб потрапити у відповідний квадрат лабіринту, стартуючи з початкового розташування.
Зміну елементів таблиці таким чином припиняємо, якщо отримано елемент першого чи останнього рядка чи стовпчика, який відмінний від 0 та 65535.
Таблицю неможливо змінити до такого вигляду, якщо сусіди останніх із змінених елементів відмінні від 0, а самі ці останні із змінених елементів розташовані поза першим і останнім рядком чи стовпчиком.
Пошук найкоротшого шляху здійснюємо «з кінця»: починаючи з останнього елемента таблиці, якому поміняли величину, переходимо до найближчого по вертикалі чи горизонталі сусіднього елемента, величина якого на 1 менша від величини розглядуваного елемента.