Как найти последнюю цифру возведения в степень ряда чисел?

Question

[Snelsi]

Какой самый оптимальный способ найти последнюю цифру выражения x1 ^ (x2 ^ (x3 ^ (x4 ^ ( ... ^xn)))) при условии, что значения x могут быть очень большими (больше шести цифр)?

В теории, нам достаточно знать только последнюю цифру x1 и две последние цифры внешней скобки, но какой алгоритм сведения остальных членов?

Comments

[YURIY KOZLOV]

Я бы не стал зарываться глубоко в теорию, но посидел с ручкой и бумажкой.
Определяющей является последняя цифра первого числа.
1 всегда даст 1
5 -> 5
6 -> 6
4 -> 6 ->4
9 -> 1 -> 9
2- 4 - 8 - 6 -2
7 - 9 - 3 - 1 - 7
8 - 4 - 2 - 6 - 8

Следовательно, при 1,5,6 на конце остальные числа не важны.
При 4,9 - важно только четная или нечетная степень, а следовательно, четное или нет второе число.
С остальными сложнее, там надо поиграться с остатком от желания второго числа на 4, и, как следствие - со значением х3, возможно х4...
Простите, дальше развивать идею не буду, попробуйте сами.

[Snelsi]

YURIY KOZLOV, Забываете, что степень ноль может дать единицу. А так код нахождения последней цифры от известной степени есть, вопрос заключался немного в другом.

[YURIY KOZLOV]

Snelsi, про нулевую степень действительно забыл, сорри.
А в чем тогда заключался вопрос? Что я не так понял?

[Snelsi]

YURIY KOZLOV, Числа xn могуть быть больше шести цифр, что делает невозможным простое возведение в степень. Вопрос был в самом оптимальном алгоритме упрощения этих значений для работы только со значущей частью, как например, урезание всей первой скобки до двух последних цифр (ведь всё что выше обнулится остачей на четыре), только в масштабе всех степеней.

[YURIY KOZLOV]

Snelsi, прошу прощения, но кажется я нигде не предлагал ПРОСТО возводить в степень. Я предлагал посидеть с карандашом и проанализировать задачу, выявить закономерности , которые помогут максимально просто получить ответ на поставленный вопрос.

[YURIY KOZLOV]

Snelsi, раз получилось непонятно, поясню свою мысль.
При х2=0 - ответ единица.
При х3=0 - ответ совпадает с последней цифрой х1.
Если ноль встречается выше, это роли не не играет.
Если эти два условия не выполняются :
Последняя цифра
х1= 0, 1, 5, 6 -> ответ совпадает с этой последней цифрой.
При последней цифре
х1 = 4 или 9 - значение имеет только четность х2, при нечетном - ответ совпадает с последней цифрой. При четном - 6 и 1, соответственно.
Для цифр 2,3,7,8 - проверять нужно на самом деле только числа х2 и х3, числа выше (если я нигде не ошибся) значения не имеют. И возводить в степень вообще нет необходимости.

[Snelsi]

YURIY KOZLOV, Действительно! Вы были правы, извините. Повозился с алгоритмом, всё работает. Просто не знал, что цифры после x3 ничего не значат (кроме нулей). Скину код ниже, тему можно закрывать.

[YURIY KOZLOV]

Snelsi, Очень рад, что идея помогла :))

Answer 1

[Snelsi]

Решение задачи на С#:

public static int LastDigit(int[] array) {
      if (array.Length == 0) return 1;
      array[0] %= 10;
      if (array.Length == 1 || array[0] == 1) return array[0];
      
      
      for (int i = 1; i < array.Length && i < 4; i++) {
        if (array[i] == 0) {
          int j = 0;
          while(i + j + 1 < array.Length && array[i + j + 1] == 0) { j++; }
          Array.Resize(ref array, i);
          if (j % 2 == 0) { array[i - 1] = 1; }
          if (i == 1) return array[0];
          break;
        }
      }
      
      if (array[0] == 0 || array[0] == 5 || array[0] == 6) return array[0];
      if (array[0] == 4) { return (array[1] % 2 == 0) ? 6 : 4; }
      if (array[0] == 9) { return (array[1] % 2 == 0) ? 1 : 9; }


      if (array.Length > 2) array[1] = (int)BigInteger.ModPow(array[1], array[2], 100);
      if (array[1] == 0) array[1] = 4;
      return (int)BigInteger.ModPow(array[0], array[1], 10);
}

Answer 2

[Владимир Олохтонов]

Вам нужен результат возведения в степень в кольце вычетов по модулю 10, начать можно вот отсюда:
https://ru.wikipedia.org/wiki/Возведение_в_степень...

Ещё можно часть про теорию чисел вот здесь посмотреть:
https://stepik.org/course/4603