UniLecs #178. Детский утренник

Задача: в детском саду дети проводили утренник, его пришли посмотреть родители детей. Воспитатель рассадила всех родителей в зале из n рядов и m кресел: сначала в первый ряд зала слева направо, дальше во второй ряд слева направо и т.д. Так как родители сильно шумели, воспитатель рассадила их по-другому: сначала заполнила все первые места от первого ряда к последнему, затем вторые места и т.д.

Определите, сколько родителей после пересадки в зале останутся на своем месте.

Входные данные: n - количество рядов в зале, m - количество кресел в ряду. n, m - натуральные числа от 1 до 10^9.

Вывод: количество родителей, которые останутся сидеть на своем прежнем месте.

Пример: n = 3, m = 3

7 8 9

4 5 6

1 2 3

3 6 9

2 5 8

1 4 7

Answer: 3 (места 1, 5, 9)

Идея:

1. Перебор: самый простой и понятный способ - это заполнение 2х массивов и последующее сравнение соот-х элементов. Считаем кол-во пар (i,j), для которых arr_1[i, j] == arr_2[i, j].
2. Используем свойства НОД: Если задать места в зале в виде матрицы, то получаем следующее (матрица зеркально отражается наверх):

Места зала до пересадки:

1 2 3

4 5 6

7 8 9

Места зала после пересадки:

1 4 7

2 5 8

3 6 9

Частный случай: n = m. Для квадратной матрицы (в зале кол-во рядов совпадает с кол-вом кресел в ряду), пересадка это обычное транспонирование матрицы. А при транспонировании квадратной матрицы на своих местах остаются только элементы главной диагонали.

Поэтому для квадратной матрицы ответ = n = m.

Общий случай: n - кол-во рядов, m - кол-во кресел в ряду. (i, j) - координаты в матрице, где i - от 0 до n - 1, j - от 0 до m - 1.

• Формула 1го варианта рассадки людей: Arr(i,j) = i * m + j + 1
• Формула 2го варианта рассадки людей: Arr(i,j) = j * n + i + 1

Сколько людей остались сидеть на тех же местах?! Приравниваем две формулы:

i * m + j + 1 = j * n + i + 1

i * m + j = j * n + i

i * m - i = j * n - j

i * (m - 1) = j * (n - 1)

i / j = (n - 1) / (m - 1)

Здесь по сути нужно найти все натуральные решения (i, j) уравнения. Кол-во таких пар равно ровно НОД(n - 1, m - 1). Также добавим значение (0, 0), эти координаты также не изменятся после перестановки.

Итого: получаем что кол-во родителей, которые останутся на своим местах равно: НОД(n - 1, m - 1) + 1.

Реализация:

Вариант 1 - перебор:

https://gist.github.com/unilecs/62f77200f629196ddd0e574cb5d9bc32

Play-test: https://dotnetfiddle.net/Hqv5z2

Вариант 2 - с помощью НОД:

https://gist.github.com/unilecs/c263115ed407b6ff317dd07d00450cd9

Play-test: https://dotnetfiddle.net/31SzDn