Килгор_Траут все записи автора Даются три целых положительных числа - x, y и n. Надо найти n-нную цифру числа (x^y) если считать справа. Пример: если x=7, y=11, n=5, ответ будет 2 (7^11=1977326743). Я знаю несколько разных способов (в духе x^y % 10^n), но загвоздка в том, что все должно работать в o(lg y), x и n принимаются за постоянные. Кто-нибудь знает достойный алгоритм?

АПДЕЙТ: Если кого-то здесь еще интересует эта задачка, предоставляю решение. Предупреждаю сразу - оно довольно-таки издевательское. Однако задача, как я уже упоминал, чисто теоретическая, и с теоретической точки зрения решение абсолютно правильное.

Итак, начинаем методически умножать число x на себя, получая x^2, x^3 и т. д. В каждом из этих чисел запоминаем последние n цифр. Рано или поздно эти цифры начнут повторяться. Как только это происходит, останавливаем процесс, запоминаем последнюю степень (назовем ее d) и считаем y%(d-s), где s является повтрояемой степенью. Затем вспоминаем какой была n-ная цифра справа у числа x^(y%(d-s)), и ответ у нас в кармане.

Пример: x=2, y=345, n=2

Число --> Последние 2 цифры
2^1 ----> 02
2^2 ----> 04
2^3 ----> 08
2^4 ----> 16
2^5 ----> 32
2^6 ----> 64
2^7 ----> 28
2^8 ----> 56
2^9 ----> 12
2^10 ---> 24
2^11 ---> 48
2^12 ---> 96
2^13 ---> 92
2^14 ---> 84
2^15 ---> 68
2^16 ---> 36
2^17 ---> 72
2^18 ---> 44
2^19 ---> 88
2^20 ---> 76
2^21 ---> 52
2^22 ---> 04 Сравните с 2^2 - то же самое! Здесь останавливаемся.
2^23 ---> 08
2^24 ---> 16 Дальше, естественно, все повторяется по новой.

Теперь находим 345 % (22-2) = 5. 2^5 дает 32, значет искомая цифра - 3.

Факт повторения последних цифр гарантируется ограниченным количеством комбинаций (10^n) и независимостью последних n цифр от цифр порядка n+1 и больше (это видно при умножении в столбик). Так как в алгоритме число y появляется лишь в конце, можно сказать что алгоритм работает в O(1) =) (вспомним, что x и n принимаются за постоянные). С практической точки зрения алгоритм практически бесполезен, так как для больших x и n нахождение закономерности может занять ОЧЕНЬ много времени. Проще сначала высчитать x^y, а потом уже найти n-ную цифру.