C ++ последняя цифра случайной последовательности степеней

Question

Я понимаю, что уже есть несколько тем, посвященных этому.Но мой вопрос не в том, как построить такой алгоритм, а в том, чтобы выяснить, какую ошибку я допустил в своей реализации, из-за которой один из десятков тестов не прошел.

Задача :снабженный std::list<int> случайными числами, определите последнюю цифру x1 ^ (x2 ^ (x3 ^ (... ^ xn))).Эти числа достаточно велики, или списки достаточно длинные, чтобы результат был астрономическим и не мог быть обработан традиционными средствами.

Мое решение : я решил использовать модульный арифметический подход.Короче говоря, последняя цифра этих огромных способностей будет такой же, как и уменьшенная мощность, состоящая из первой цифры основания (мод 10), увеличенной до последних двух цифр экспоненты (мод 100).Единицы в последовательности степеней повторяются не более 4, поэтому мы можем использовать мод 4, чтобы уменьшить показатель степени, смещение на 4, чтобы избежать остатков 0. По крайней мере, это мое понимание этого до сих пор, основанное на следующемресурсы: блестящий / квора .

#include <list>
#include <cmath>

int last_digit(std::list<int> arr)
{
  // Break conditions, extract last digit
  if (arr.size() == 1) return arr.back() % 10;
  if (arr.size() == 0) return 1;

  // Extract the last 2 items in the list
  std::list<int> power(std::prev(arr.end(), 2), arr.end());
  arr.pop_back(); arr.pop_back();

  // Treat them as the base and exponent for this recursion
  long base = power.front(), exponent = power.back(), next;

  // Calculate the current power
  switch (exponent)
  {
    case  0: next = 1; break;
    case  1: next = base % 100; break;
    default: next = (long)std::pow(base % 10, exponent % 4 + 4) % 100;
  }
  if (base != 0 && next == 0) next = 100;

  // Add it as the last item in the list
  arr.push_back(next);

  // Recursively deal with the next 2 items in the list
  return last_digit(arr);
}

Случайный пример : 123,232 ^{694,027 140,249} * 8

• Первое пополнение: { 123'232, 694'027, 140'249 }
  • база: 694 027 мод 10 = 7
  • показатель степени: 140 249 мод 4 + 4 = 5
  • следующий: 7 ⁵ = 16,807 мод 100 = 7
• Вторая рекурсия: { 123'232, 7 }
  • база: 123 232 мод 10 = 2
  • показатель степени: 7 мод 4 + 4 = 7
  • следующий: 2 ⁷ = 128 мод 100 = 28
• Третья рекурсия: { 28 }
  • возврат: 28 мод 10 = 8

Проблема : это работает для десятков тестовых случаев(как показано выше), но не работает в течение 2 ^{2 101 2} ≡6.
От руки:

• 101 ² = 10,201
• 2 ^10,201 мод 4 = 0, + 4 = 4
• 2 ⁴ = 16 // 6 -correct

Однако, следуя алгоритму:

• Первая рекурсия: { 2, 2, 101, 2 }
  • база: 101 мод 10 = 1
  • показатель степени: 2 мод 4 + 4 = 6
  • следующий: 1 ⁶ = 1 мод 100 = 1
• Вторая рекурсия: { 2, 2, 1 } (мы уже можем видеть, что результат будет 4)
  • экспонента = 1, следующий = 2 мод 100 = 2
• Третья рекурсия: { 2, 2 }
  • база: 2 мода 10 = 2
  • показатель степени: 2 мода 4 + 4 = 6
  • следующий: 2 ⁶ = 64 mod 100 = 64
• Четвертая рекурсия: { 64 }
  • return 64 mod 10 = 4 // -wrong

В некотором смысле, я вижу, что происходит, но я не совсем уверен , почему это происходит для этого конкретного случая, а не для десятковдругие.Я признаю, что я скорее раздвигаю границы моих знаний по математике, но у меня складывается впечатление, что я просто упускаю крошечную часть головоломки.

Я считаю, что этот пост достаточно длинный и трудный, как он есть,Если у кого-то есть понимание того, где я ошибаюсь, я буду признателен за некоторые советы.