Для базы 3:
3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...
То есть цифра единиц имеет только 4 возможности, а затем она повторяется в одном и том же цикле.
С помощью теоремы Эйлера мы можем показать, что это верно для любого целого числа n, означающего, что цифра их единиц будет повторяться после не более 4 последовательных показателей. Просмотр только числа единиц произвольного произведения эквивалентен взятию остатка умножения по модулю 10, например:
2^7 % 10 = 128 % 10 = 8
Также можно показать (и довольно интуитивно понятно), что для произвольной базы цифра единиц любой мощности будет зависеть только от цифры единиц самой базы - то есть 2013 ^ 2013 имеет ту же цифру единиц, что и 3 ^ 2013.
Мы можем использовать оба факта для создания чрезвычайно быстрого алгоритма (спасибо за help - с любезного разрешения я могу представить намного более быструю версию).
Идея такова: поскольку мы знаем, что для любого числа 0-9 будет не более 4 различных результатов, мы можем также сохранить их в таблице поиска:
{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4,
5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }
Это возможные результаты для 0-9 в этом порядке, сгруппированные по четыре. Идея теперь для возведения в степень n ^ a до
- сначала возьми базовый мод 10 =>: =
i
- перейти к индексу
4*i в нашей таблице (это начальное смещение этой конкретной цифры)
- возьмите показатель степени 4 =>: =
off (как указано в теореме Эйлера, у нас есть только четыре возможных результата!)
- добавьте
off к 4*i, чтобы получить результат
Теперь, чтобы сделать это как можно более эффективным, к базовым арифметическим операциям применены некоторые настройки:
- Умножение на 4 эквивалентно сдвигу влево на два ('<< 2') </li>
- Взятие числа
a % 4 эквивалентно произнесению a&3 (маскировка 1 и 2 бита, которые образуют остаток% 4)
Алгоритм в C :
static int table[] = {
0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4,
5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};
int /* assume n>=0, a>0 */
unit_digit(int n, int a)
{
return table[((n%10)<<2)+(a&3)];
}
Подтверждение первоначальных претензий
Из наблюдений мы заметили, что цифра единиц для 3 ^ x повторяется в каждой четвертой степени. Утверждение состояло в том, что это верно для любого целого числа. Но как это на самом деле доказано? Оказывается, с помощью модульной арифметики довольно легко. Если нас интересует только цифра единиц измерения, мы можем выполнить наши вычисления по модулю 10. Это эквивалентно тому, что цифры единиц измерения повторяются после 4 показателей или
a^4 congruent 1 mod 10
Если это так, то, например,
a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10
то есть, ^ 5 дает ту же цифру, что и ^ 1 и т. Д.
Из по теореме Эйлера мы знаем, что
a^phi(10) mod 10 = 1 mod 10
где phi (10) - это числа от 1 до 10, которые взаимно просты с 10 (то есть их gcd равен 1). Числа <10, взаимно простые с 10, равны 1,3,7 и 9. Итак, phi (10) = 4, и это доказывает, что на самом деле <code>a^4 mod 10 = 1 mod 10.
Последнее утверждение, которое нужно доказать, состоит в том, что для возведения в степень, где база> = 10, достаточно просто взглянуть на цифру единиц базы. Допустим, наша база x> = 10, поэтому мы можем сказать, что x = x_0 + 10 * x_1 + 100 * x_2 + ... (представление базы 10)
Используя модульное представление, легко увидеть, что действительно
x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10
где a_i - коэффициенты, которые включают степени x_0, но, в конечном итоге, не имеют значения, поскольку все произведение a_i * (10 * x_i) ^ y-i будет делиться на 10.