Множення у діедральній групі#6242

Множення у діедральній групі

5 секунд

128 мегабайтів

Легка

Діедральна група — це множина $D$ з операцією множення $*$ , визначеною на $D$ . Множина $D$ породжується двома елементами $a$ та $b$ . Операція множення $*$ явно не записується, тобто $a * a$ a*a буде позначатись як $aa$ або $a^{2}$ a^2. Аналогічно, $a * a * b$ a*a*b записується як $a^{2} b^{1}$ a^2b^1 або просто $a^{2} b$ a^2b.

Діедральна група $D$ має два цілі параметри $m$ і $n$ , де $m \geq 2$ m \geq 2 і $n \geq 2$ n \geq 2, тому діедральну групу записують як $D_{m, n}$ D_{m,n}. Відношення, що визначають $D_{m, n}$ D_{m,n}, такі:

$a^{m} = a^{0} = 1$ a^m = a^0 = 1, $b^{n} = b^{0} = 1$ b^n = b^0 = 1 і $ba = a^{m - 1} b$ ba = a^{m-1}b.

Отже, $D_{m, n}$ D_{m,n} має $mn$ елементів, а саме

$D_{m, n} = {a^{j} b^{k} ∣0 \leq j < m, 0 \leq k < n} = {a^{0} b^{0}, a^{1} b^{0}, a^{2} b^{0}, \dots, a^{m - 1} b^{0}, \dots, a^{m - 1} b^{n - 1}}$ D_{m,n} = \{ a^j b^k | 0 \leq j < m, 0 \leq k < n \} = \{ a^0b^0, a^1b^0, a^2b^0, \ldots, a^{m-1}b^0, \ldots, a^{m-1}b^{n-1} \}.

Наприклад, нехай $m = 7$ m = 7 і $n = 2$ n = 2. Елементи $D_{7, 2}$ D_{7,2}:

${a^{0} b^{0}, a^{1} b^{0}, a^{2} b^{0}, a^{3} b^{0}, a^{4} b^{0}, a^{5} b^{0}, a^{6} b^{0}, a^{0} b^{1}, a^{1} b^{1}, a^{2} b^{1}, a^{3} b^{1}, a^{4} b^{1}, a^{5} b^{1}, a^{6} b^{1}}$ \{ a^0b^0, a^1b^0, a^2b^0, a^3b^0, a^4b^0, a^5b^0, a^6b^0, a^0b^1, a^1b^1, a^2b^1, a^3b^1, a^4b^1, a^5b^1, a^6b^1 \}.

Множення не є комутативним, тобто $ba \neq = ab$ ba \neq ab. Насправді $ba = a^{6} b$ ba = a^6b згідно з визначальними відношеннями $D_{7, 2}$ D_{7,2}. Також $a^{j} a^{k} = a^{(j + k) % m}$ a^ja^k = a^{(j+k) \% m}, і $b^{j} b^{k} = b^{(j + k) % n}$ b^jb^k = b^{(j+k) \% n}. Отже:

$(a^{j} b^{k}) (a^{p} b^{q}) \neq = (a^{(j + p) % m} b^{(k + q) % n})$ (a^jb^k)(a^pb^q) \neq (a^{(j+p) \% m}b^{(k+q) \% n}).

Щоб правильно перемножити два елементи $(a^{3} b^{1})$ (a^3b^1) і $(a^{2} b^{1})$ (a^2b^1) із $D_{7, 2}$ D_{7,2}, виконаємо такі дії:

$(a^{3} b^{1}) (a^{2} b^{1}) = (a^{3} b^{0}) (ba) (a^{1} b^{1}) = (a^{3} b^{0}) (a^{6} b^{1}) (a^{1} b^{1})$ (a^3b^1)(a^2b^1) = (a^3b^0)(ba)(a^1b^1) = (a^3b^0)(a^6b^1)(a^1b^1),

оскільки $ba = a^{6} b$ ba = a^6b.

Оскільки $a^{3} b^{0} a^{6} = a^{3} a^{6} = a^{(3 + 6) %7} = a^{2}$ a^3b^0a^6 = a^3a^6 = a^{(3+6) \% 7} = a^2, помножимо перші два множники: $(a^{3} b^{0}) (a^{6} b^{1}) = (a^{2} b^{1})$ (a^3b^0)(a^6b^1) = (a^2b^1).

Отже,

$(a^{3} b^{0}) (a^{6} b^{1}) (a^{1} b^{1}) = (a^{2} b^{1}) (a^{1} b^{1})$ (a^3b^0)(a^6b^1)(a^1b^1) = (a^2b^1)(a^1b^1).

Тепер перезапишемо вираз так:

$(a^{2} b^{1}) (a^{1} b^{1}) = (a^{2} b^{0}) (ba) (a^{0} b^{1}) = (a^{2} b^{0}) (a^{6} b^{1}) (a^{0} b^{1}) = (a^{8} b^{2}) = (a^{1} b^{0})$ (a^2b^1)(a^1b^1) = (a^2b^0)(ba)(a^0b^1) = (a^2b^0)(a^6b^1)(a^0b^1) = (a^8b^2) = (a^1b^0).

Отже, добуток двох елементів $(a^{3} b^{1})$ (a^3b^1) та $(a^{2} b^{1})$ (a^2b^1) дорівнює $(a^{3} b^{1}) (a^{2} b^{1}) = (a^{1} b^{0})$ (a^3b^1)(a^2b^1) = (a^1b^0).

Ваше завдання — написати програму, яка, отримавши $m$ , $n$ та будь-які два елементи $(a^{j} b^{k})$ (a^j b^k) та $(a^{p} b^{q})$ (a^p b^q) діедричної групи $D_{m, n}$ D_{m,n}, коректно обчислює їхній добуток.

Вхідні дані

Вхідні дані складаються з кількох тестів. Кожен тест займає кілька рядків. Перший рядок кожного тесту містить problemID, $m$ , $n$ та $p$ , відокремлені пробілом. Значення $m$ і $n$ не перевищують $1000$ . Число $p$ — кількість прикладів на множення у поточному тесті. Далі йде $p$ рядків, кожен з яких містить два елементи з $D_{m, n}$ D_{m,n}, які треба помножити. Кожен елемент задано у вигляді a3b1 замість $a^{3} b^{1}$ a^3b^1. Дані для наступного тесту йдуть одразу за попереднім. Якщо problemID дорівнює ZZ, це означає кінець вхідних даних.

Вихідні дані

Для кожного прикладу на множення потрібно вивести один рядок у такому вигляді:

ProblemID id: ajbk * apbq = arbs

де id — це номер problemID з вхідних даних, ajbk та apbq — елементи, які треба помножити, а arbs — правильна відповідь.

Приклади

Приклад 1