Задача №113979. Дискретное показательное уравнение
|
Часто операции с числами ведутся по модулю какого-либо числа \(p\), например, \(a \uparrow_p b = a^b \bmod{p}\). Напишите программу, которая для заданных величин \(p\) и \(a\) будет находить все решения \(b_i\) и \(c_j\) уравнения \(a \uparrow_p b_i = c_j \bmod p\), выбираемые из заданных множеств. Нужно разделить исходные множества чисел \(b\) и \(c\) на пары соответствующих друг другу наборов: любое число \(b\) и любое число \(c\) из пары наборов удовлетворяют указанному уравнению.
В первой строке через пробел заданы два целых числа \(p\) и \(a\) (\(1 \leq a, p \leq 10^9\)). Во второй строке задано целое число \(n\) — размер набора целых чисел \(\{b_i\}\), которые через пробел перечислены в третьей строке. В четвёртой строке задано целое число \(m\) — размер набора целых чисел \(\{c_j\}\), которые через пробел перечислены в пятой строке. Выполнены ограничения \(1 \leq n,m \leq 10^5\); \(0 \leq b_i, c_j \leq 10^9\).
Результирующие пары наборов нужно вывести парами строк: в первой строке из пары содержится набор чисел \(b\), во второй — набор чисел \(c\). В начале каждой строки выводится количество чисел в соответствующем наборе. Если какому-то набору \(b\) не соответствует ни одного \(c\) или какому-то набору \(c\) не соответствует ни одного \(b\), то для такого набора строка, представляющая парный набор, должна содержать только \(0\). Порядок перечисления чисел в наборе и порядок перечисления пар наборов могут быть любыми.
\((4^3 \bmod 5 = 64 \bmod 5) = (4^1 \bmod 5 = 4 \bmod 5) = 9 \bmod 5\); \(4^2 \bmod 5 = 16 \bmod 5 = 1\), \(4^4 \bmod 5 = 256 \bmod 5 = 1\), ни одно из остальных чисел \(c_j\) не даёт остаток \(1\) при делении на \(5\).
5 4 4 1 2 3 4 6 2 10 5 9 7 17
2 1 3 1 9 2 2 4 0 0 5 10 5 2 7 17