Случайная задача

Автор и разработчик задачи: Ильдар Гайнуллин

Давайте выберем случайное простое число $$$p$$$ в районе $$$\sqrt{n}$$$.

Для каждой тройки $$$(x_1 \bmod p, y_1 \bmod p, x_2 \bmod p)$$$ с $$$y_1 \bmod p > 0$$$ найдем $$$y_2 \bmod p$$$ с нужным значением $$$(x_1 \cdot y_1 + x_2 \cdot y_2) \bmod p$$$, давайте обозначим его за $$$f_{x_1, y_1, x_2}$$$.

После этого, для фиксированного $$$i$$$ с $$$y_i \bmod p > 0$$$ зафиксируем $$$x_j \bmod p$$$, проверим все точки с таким значением $$$x$$$ по модулю и $$$y_j \bmod p = f_{x_i,y_j,x_j}$$$.

Для точек с $$$y_i \bmod p$$$ проверим точки с $$$(x_j \cdot x_i) \bmod p = k \bmod p$$$.

Почему это работает быстро? Посмотрим на фиксированную пару $$$x_i \cdot x_j + y_i \cdot y_j \neq k$$$, но для которой выполняется равенство $$$\mod p$$$. Есть $$$O(1)$$$ таких $$$p$$$, для которых это было бы верно. Так как если бы это выполнялось для большого количества простых модулей, по китайской теореме об остатках получилось бы, что равенство без модуля тоже верно. Поэтому, вероятность того, что фиксированная пара даст равенство по случайному модулю примерно равна $$$(\frac{1}{\sqrt{n}/log{n}})$$$. А значит, матожидание количества таких пар равно $$$n^2 \cdot \frac{\log{n}}{\sqrt{n}} = n \cdot \sqrt{n} \log{n}$$$.

Поэтому, если бы точки были не случайны, задачу можно было бы решить за $$$n \cdot \sqrt{n} \log{n}$$$.

Но точки случайны, поэтому $$$(x_i \cdot x_j + y_i \cdot y_j) \bmod p$$$ тоже случайно, поэтому есть примерно $$$n \cdot \sqrt{n}$$$ пар точек при фиксированном значении модуля.

Поэтому, всю задачу можно решить за $$$n \cdot \sqrt{n}$$$.