Во-первых, вы не можете сохранить значение в строке, потому что 2 10000 цифр намного больше, чем общее количество частиц во вселенной (10 80 ≈ 2 265.75 ). Вам даже не хватит памяти, если вы храните ее в битах (фактически, библиотеки bigint хранят свои числа, а хорошие библиотеки не хранят значения в виде символов)
Итак, вы можете использовать модульное возведение в степень , чтобы получить по модулю. В основном вы используете свойство (a * b) % M = ((a % M) * (b % M)) % M, чтобы избежать вычисления реальной мощности. Многие языки уже имеют встроенную поддержку для этого, например, Python pow функция имеет необязательный третий аргумент для этого, что приводит к pow(base, exp[, mod]). Реализация точно такая же, как у обычного pow, просто замените power *= base на modpow = (modpow * base) % M. Есть много примеров по SO
You не нужно l oop (2 n - 1) k раз. Это на самом деле невозможно, потому что при условии, что вы можете l oop 2 32 раз в секунду, вам понадобится 2 32 секунд - 136 лет до l oop 2 64 раза. Представьте, сколько веков нужно считать до 2 10000 . К счастью, результат повторится после цикла, вам просто нужно рассчитать длину цикла
Вот те подсказки, которые нужны. Вы можете сослаться на , как рассчитать ^ (b ^ c) mod n? и , найдя ^ b ^ c ^ ... mod m , которые ближе к вашей проблеме