Подскажите, как решать эту задачу.

В обсуждениях есть решение вида: понятно, что для удобных чисел верно a² = b·10ⁿ + a, следовательно a(a - 1) делится на 10ⁿ. Отсюда одно из чисел a,(a - 1) делится на 5ⁿ, другое — на 2ⁿ. Другими словами, a ≡ 1(mod2ⁿ) или a ≡ 2ⁿ - 1(mod2ⁿ) при условии, что a = 5ⁿ·k. Из этих равенств найдём а расширенным алгоритмом Евклида. Если найденный ответ состоит меньше, чем из n цифр, то его не считаем. Но это решение имеет сложность O(n⁴) (я прав?): алгоритм Евклида работает в среднем за О(log(a)) = O(n), на каждом его шаге происходит длинное деление за O(n²) (можно быстрее, но не уверен, что это поможет), и всё это надо повторить для всех N.

Есть другая идея за О(n³): запишем число 5ⁿ в бинарном виде. За O(n²) найдём такие k₁ и k₂,что 5ⁿ·k₁ заканчивается на 00...001, а 5ⁿ·k₂ заканчивается на 111...11 — это и будут искомые числа. Ввиду больших констант и n = 2000 это решение также по-видимому не актуально.

Спасибо заранее за любую помощь.