Прочтение замечательного текста от peltorator https://mirror.codeforces.com/blog/entry/91258 натолкнуло меня на мысль о том, что мне не известно ни одного ресурса по спортивному программированию, где было бы изложено то, что известно про структуру группы $$$(\mathbb{Z}/m\mathbb{Z})^*$$$ (группа остатков по модулю $$$m$$$, взаимнопростых с $$$m$$$). Поскольку звучит это очень математично и бесполезно, то приведу пример, когда такое знание может быть полезно. Например, мы хотим решать такую задачу: дано число $$$m$$$ и много запросов вида $$$a, b$$$, где $$$(a, m) = (b, m) = 1$$$, и мы хотим решать уравнение вида $$$a^x = b \mod m$$$. Для некоторых $$$m$$$ (для которых существует первообразный корень) задача решается при помощи baby-step-giant-step, подробнее можно прочитать по ссылке выше. По сути мы пользуемся тем, что в этих случаях $$$(\mathbb{Z}/m\mathbb{Z})^* \cong \mathbb{Z}_{\varphi(m)}$$$. Однако, оказывается, что и для других $$$m$$$ нам известна структура этой группы, и мы можем применить это знание для решения нашей задачи!
Disclaimer: на этом страшные слова про группы закончились, дальнейший текст я постарался сделать максимально простым и не использующим всякие ругательства. В частности это означает, что доказательств в тексте ниже не будет.
Итак, мы хотим быстро решать задачи вида $$$a^x = b \mod m$$$, где $$$(a, m) = (b, m) = 1$$$, но само $$$m$$$ не является простым, причем отвечать нам придется на много запросов вида $$$a, b$$$, а $$$m$$$ будет фиксированным. Для того, чтобы сделать это, давайте сначала факторизуем $$$m$$$. Итак, пусть $$$m = 2^{\alpha_0}p_1^{\alpha_1}\dotsc p_{n}^{\alpha_n}$$$. Для удобства, иногда мы будем использовать обозначение $$$p_0 = 2$$$ (Как будет видно ниже, оно существенно отличается от остальных простых. Это связано с тем, что по модулю $$$2^{\alpha}$$$ при $$$\alpha > 2$$$ не существует первообразных корней). Введем также обозначения $$$q_i = m / p_i^{\alpha_i}$$$. Оказывается, что если взять
- $$$g_{-1} = -1 \mod 2^{\alpha_0}, g_{-1} = 1 \mod q_0$$$;
- $$$g_{0} = 5 \mod 2^{\alpha_0}, g_{0} = 1 \mod q_0$$$;
- $$$\forall \; i > 0: g_{i}$$$ — первообразный корень по модулю $$$p_i^{\alpha}, g_{i} = 1 \mod q_i$$$,
то любой взаимнопростой с $$$m$$$ остаток будет иметь вид $$$g_{-1}^{\beta_{-1}}g_{0}^{\beta_{0}}\dotsc g_{n}^{\beta_n}$$$, причем будут выполняться неравенства $$$\beta_i \in [0, m_i)$$$, где $$$m_i = p_{i}^{\alpha_i - 1}(p_{i} - 1), i > 0$$$, $$$m_{-1} = 1 + \chi(\alpha_0 > 1)$$$, $$$m_0 = \max(1, 2^{\alpha_0 - 2})$$$. Более того, можно доказать, что такое представление будет единственным!
Теперь попытаемся научиться раскладывать элемент по нашему базису. Конечно, мы будем делать это при помощи meet-in-the-middle, однако нам придется несколько модифицировать алгоритм. Давайте зафиксируем некоторое $$$K$$$ и посмотрим на минимальное такое $$$i$$$, что $$$m_{-1}\dotsc m_{i} \geq K$$$. Тогда, очевидно, есть такое число $$$L$$$, что $$$m_{-1}\dotsc m_{i - 1}\lfloor m_i / L\rfloor \in [K/2, K]$$$. Давайте теперь предподсчитаем все числа вида $$$g_{-1}^{\beta_{-1}}g_{0}^{\beta_{0}}\dotsc g_{i - 1}^{\beta_{i-1}}g_i^{\beta_{i}}$$$ с условиями $$$\beta_{j} \in [0, m_j), L \vert \beta_{i}$$$. Таких чисел будет порядка $$$K$$$. Теперь на запрос нам достаточно перебрать все числа вида $$$p_i^{\beta_i}\dotsc p_n^{\beta_n}$$$ с условиями $$$\forall \; j > i: \beta_{j} \in [0, m_j), \beta_{i} \in [0, L)$$$ и проверить, что среди предподсчитаных чисел есть то, которое в произведении с этим дает $$$a$$$. Очевидно, что такое решение работает за $$$O(K\log K)$$$ предподсчета и $$$O(\varphi(m)\log K / K)$$$ на запрос.
Осталось понять, как по разложению в таком базисе двух чисел понять, в какую степень надо возвести первое, чтобы получить второе. Это не очень сложно, поскольку возведение в степень в таком представлении просто умножает коэффициенты по модулю. Другими словами, если разложение $$$a$$$ имеет вид $$$(a_{-1}, \dotsc, a_n)$$$, то разложение $$$a^x$$$ будет иметь вид $$$(a_{-1}x \mod m_{-1}, \dotsc, a_nx \mod m_n)$$$. Таким образом, получаем систему $$$x = b_i / a_i \mod m_i$$$. Решая ее (или понимая, что она не имеет решения) при помощи КТО, получаем ответ на запрос.
