Подскажите, как решать эту задачу.
В обсуждениях есть решение вида: понятно, что для удобных чисел верно a2 = b·10n + a, следовательно a(a - 1) делится на 10n. Отсюда одно из чисел a,(a - 1) делится на 5n, другое — на 2n. Другими словами, a ≡ 1(mod2n) или a ≡ 2n - 1(mod2n) при условии, что a = 5n·k. Из этих равенств найдём а расширенным алгоритмом Евклида. Если найденный ответ состоит меньше, чем из n цифр, то его не считаем. Но это решение имеет сложность O(n4) (я прав?): алгоритм Евклида работает в среднем за О(log(a)) = O(n), на каждом его шаге происходит длинное деление за O(n2) (можно быстрее, но не уверен, что это поможет), и всё это надо повторить для всех N.
Есть другая идея за О(n3): запишем число 5n в бинарном виде. За O(n2) найдём такие k1 и k2,что 5n·k1 заканчивается на 00...001, а 5n·k2 заканчивается на 111...11 — это и будут искомые числа. Ввиду больших констант и n = 2000 это решение также по-видимому не актуально.
Спасибо заранее за любую помощь.
Посмотрел свое старое решение, там один захардкоженный массив чисел, видимо как-то предпосчитанный. В уральских олимпиадах такое встречается, что надо предпосчитать чего-то. Алгоритм Евклида можно делать не за O(n^3) а за O(n^2) см wiki "бинарный алгоритм евклида" тогда сложность будет O(n^3). Если числа представлять в двоичном виде как массив 32-х битовых значений, кол-во операций будет примерно n * n / 32 для одного вызова GCD, для прекалька вполне хватает, даже в секунду можно постараться впихнуть.
Спасибо! Не знал про бинарный алгоритм Евклида, попробую написать.
Мне помогло знание вот такой штуки: http://www.youtube.com/watch?gl=RU&v=lUuFRg0aZTw
Как точно решать, не помню, это было 2 года назад. Вот код: http://pastebin.com/8AaXdHyc. Работает, правда, долго, 1.5 секунды при TLE = 2.
Вроде там работает такая магия — есть две серии ответов, ...2890625 и ...7109376. Чтобы получить следующую цифру, надо для первой серии просто возвести число в квадрат и взять следующую цифру(к примеру, 90625^2=8212**890625**, 890625^2=79321**2890625**). Для второй серии поступаем аналогично, только берем 10 - (следующая цифра). Т. е. 376^2=14**1376**, следующая цифра 10 - 1 = 9 и так далее.
А ещё правда, что число из первой серии = 10L + 1 — число из второй серии, так что можно считать только одну.
Или найти ответ для 2000 и брать суффиксы, для которых свойство тоже выполняется.
Мое решение основано на другой идее. Заметим, что если число вида abcd... — "волшебное" (назовем его так), то все его суффиксы также должны быть "волшебными". Тогда способ поиска чисел такой: поддерживаем множество чисел определенной длины (для длины 1 будет множество {1, 5, 6}), по множеству можно получить множество длины на единицу больше: приписываем к каждому числу слева все цифры от 0 до 9 и смотрим, удовлетворяет ли данное число свойству "волшебности", если да — добавляем его в новое множество. Проверку можно сделать за O(N), поскольку для чисел меньшей длины мы уже знаем, что они волшебные. Не знаю как доказать, но оказывается, что в каждом множестве всегда будет не более 4 чисел. Итого имеем решение сложности O(N^2)