Немного отойду от традиции и создам немного неоффтопную тему. Наверняка, здесь есть много спортивных программистов,которые интересуются теорией чисел и теорией сложности.
Специально для них (и для всех остальных желающих) хочу предложить следующую задачу:
Пускай есть циклическая группа
порядка q. Существуют два алгоритма: первый из них это некий Algo1, который работает следующим образом:
, 1 ≤ a, b ≤ q. Сторонним наблюдателям, таким как мы с вами, неизвестны ни a, ни b, ни g, ни q. Просто они формально есть, и мы знаем, что алгоритм работает таким образом.
![](https://espresso.codeforces.com/f661040e2af9bbbb0f0d192a44d31c7fcc050fe7.png)
![](https://espresso.codeforces.com/7d468e6f3e368786867d80675daa6e64b92b750f.png)
Второй из них - это некий Algo2, который работает следующим образом:
, 1 ≤ a ≤ q.
![](https://espresso.codeforces.com/ef6877ca7edc6e11b26de370efb116a82564dfba.png)
Собственно вопрос: необходимо доказать их эквивалентность в смысле сложности ( ну или говоря другими словами, показать полиномиальную сводимость друг к другу).
UPD. Для некого упрощения задачи, будем считать следующее - данная группа
задает некоторую подгруппу мультипликативной группы поля
, причем ее порядок q пусть будет пока нечетным.
![](https://espresso.codeforces.com/f661040e2af9bbbb0f0d192a44d31c7fcc050fe7.png)
![](https://espresso.codeforces.com/69090fb24fe89fdb59d77f38b669e6807ef9a41d.png)
Под эквивалетностью работы понимается следующее:
![](https://espresso.codeforces.com/ca269e3b787b740b0237ca572319f1ef0afa62c2.png)
![](https://espresso.codeforces.com/8644407dbed58e996c75e470a91e777bb8a46103.png)
В общем, пока ответа нет, я здесь написал свои соображения.
Не знаю, правильно ли єто, но попробую:
второй алго можно свести к первому: (g, ga) -> (g, ga, ga) -> (g, ga, gb).
То есть, аналогичность очевидна. А насчёт сложности - нужно поиграть с О-символикой для простого сложения или умножения функций.
Извините, был напуган.
Хотя нет, это неверно, т.к. -g^{b/2} -- не степень g и нам не гарантируют, как отработает алгоритм корректно.