Гиганты

Очевидно, что вычисление точного значения X^Y не представляется возможным в силу установленных ограничений, причем проблема здесь не только в типах данных, но и во времени и памяти, необходимыми для выполнения данной операции.

Заметим, что последняя цифра результата зависит только от последней цифры числа X, поэтому все остальные старшие разряды мы можем исключить, оставив в числе X только последнюю цифру. Далее, следует обратить внимание на то, что последняя цифра значения X⁴ совпадает с последней цифрой исходного числа X. Действительно, если взять число, оканчивающееся на 2 и умножить его на 2, то получится число, оканчивающееся на 4, при повторном умножении получим число, оканчивающееся на 8, при третьем умножении последней цифрой будет 6, а при четвертом умножении мы снова получим 2. Для всех цифр мы можем записать аналогичную последовательность преобразований:

  0 - 0 - 0 - 0 - 0              5 - 5 - 5 - 5 - 5
  1 - 1 - 1 - 1 - 1              6 - 6 - 6 - 6 - 6
  2 - 4 - 8 - 6 - 2              7 - 9 - 3 - 1 - 7
  3 - 9 - 7 - 1 - 3              8 - 4 - 2 - 6 - 8
  4 - 6 - 4 - 6 - 4              9 - 1 - 9 - 1 - 9

Поэтому, при уменьшении большого значения Y на 4 последняя цифра результата не изменится, это означает, что мы можем выполнить такое вычитание многократно и получить в результате в Y значение от 0 до 3, это значение соответствует значению Y mod 4. Для нахождения данного значения необходимо выполнить деление длинного числа на короткое, что вполне приемлемо, однако, задачу можно упростить, если искать вместо Y mod 4 значение Y mod 100. Действительно, если каждые 4 операции умножения не меняют последнюю цифру числа, то 100 операций так же ее не изменят, т.к. 100 делится на 4. Заметим, что искать остаток от деления длинного числа на 100 проще, для этого достаточно взять последние 2 цифры числа Y.

В результате получаем следующий алгоритм:

  read(sx,sy)
  x = int(right(sx,1))
  y = int(right(sy,2))+100
  p = 1
  for i=1..y
    p = p*x mod 10
  write(p) 

[Обсуждение] [Все попытки] [Задача]