Блог пользователя SendThemToHell

Автор SendThemToHell, история, 3 года назад, По-русски

Прочтение замечательного текста от 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}$$$. Оказывается, что если взять

  1. $$$g_{-1} = -1 \mod 2^{\alpha_0}, g_{-1} = 1 \mod q_0$$$;
  2. $$$g_{0} = 5 \mod 2^{\alpha_0}, g_{0} = 1 \mod q_0$$$;
  3. $$$\forall \; i > 0: g_{i}$$$ — первообразный корень по модулю $$$p_i^{\alpha_i}, 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$$$. Решая ее (или понимая, что она не имеет решения) при помощи КТО, получаем ответ на запрос.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

Автор SendThemToHell, история, 4 года назад, По-русски

Today I have discovered a strange fact about problem D from SNSS round 5.

I believe, most of the accepted solutions were something like "do ternary search over the angle/x-coordinate". It was somewhat hard for me to squeeze it into TL, so I had to do only 20 iterations to get accepted. Today I decided to find out, what is the minimum number of iterations of ternary search required to get AC. Turned out that this number is equal to... 0. The code which gives AC is listed below.

Spoiler

I believe that this code takes the intersection of the bisector of AB and the circle as optimum, which is definitely wrong. Am I missing something?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится