@Snelsi

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

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

В теории, нам достаточно знать только последнюю цифру x1 и две последние цифры внешней скобки, но какой алгоритм сведения остальных членов?
  • Вопрос задан
  • 909 просмотров
Решения вопроса 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);
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
sgjurano
@sgjurano
Разработчик
Вам нужен результат возведения в степень в кольце вычетов по модулю 10, начать можно вот отсюда:
https://ru.wikipedia.org/wiki/Возведение_в_степень...

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы