последняя цифра а^Ь^с

Question

Я застрял на эту проблему:

дан, б и три натуральные числа (например, что 1 < = а, Ь, с < = 10^9), вы должны найти последнюю цифру числа а^Ь^с.»

То, что я, во-первых мысль была O (срубы алгоритм п) для поднятия при включении питания п.

int acc=1; //accumulator 
    while(n>0) { 
     if(n%2==1) 
      acc*=a; 
     a=a*a; 
     n/=2; 
    } 

Очевидно, что некоторые основные математике может помочь, как «последняя цифра» вещи:

Last_digit(2^n) = Last_digit(2^(n%4)) 

Где п% 4 является остаток от деления п/4

В двух словах, я попытался объединить это, но я не мог поправиться.

Некоторая помощь действительно будет оценена.

Answer 1

Проблема в том, что b^c может быть очень большой. Поэтому вы хотите уменьшить его, прежде чем использовать стандартное модульное возведение в степень.

Вы можете отметить, что a^(b^c) MOD 10 может содержать не более 10 разных значений.

В силу принципа Дирихле, будет ряд p, что для некоторых r:

a^r MOD 10 = a^(p+r) MOD 10 
p <= 10 
r <= 10 

Это означает, что для любого q:

a^r MOD 10 = a^r*a^p MOD 10 
      = (a^r*a^p)*a^p MOD 10 
      = ... 
      = a^(r+q*p) MOD 10 

Для любого n = s+r+q*p, с s < p вы имеют:

a^n MOD 10 = a^s*a^(r+q*p) MOD 10 
      = a^s*a^r MOD 10 
      = a^((n-r) MOD p)*a^r MOD 10 

Вы можете просто заменить n= (b^c) в предыдущем уравнении.

Вычислите только (b^c-r) MOD p где p <= 10, что легко сделать, а затем вычислить a^((b^c-r) MOD p)*a^r MOD 10.

Answer 2

Как я уже упоминал в своих комментариях, это действительно не имеет особого отношения к интеллектуальным алгоритмам. Проблема может быть полностью сведена с использованием некоторой теории элементарных чисел. Это даст алгоритм O (1).

В китайской теореме о остатках говорится, что если мы знаем некоторое число x по модулю 2 и по модулю 5, то мы знаем это по модулю 10. Поэтому найти a^b^c по модулю 10 можно свести к нахождению a^b^c по модулю 2 и a^b^c по модулю 5. Маленькая теорема Ферма гласит, что для любого простого p, если p не делит a, то a^(p-1) = 1 (mod p), поэтому a^n = a^(n mod (p-1)) (mod p). Если p делит a, то, очевидно, a^n = 0 (mod p) для любого n> 0. Заметим, что x^n = x (mod 2) для любого n> 0, поэтому a^b^c = a (mod 2).

Остается найти a^b^c mod 5, который сводится к нахождению b^c mod 4. К сожалению, мы не можем использовать ни теорему китайского остатка, ни небольшую теорему Ферма. Тем не менее, mod 4 есть только 4 возможности для b, поэтому мы можем проверить их отдельно. Если мы начнем с b = 0 (mod 4) или b = 1 (mod 4), то, конечно, b^c = b (mod 4).Если мы имеем b = 2 (mod 4), то легко видеть, что b^c = 2 (mod 4), если c = 1 и b^c = 0 (mod 4), если c> 1. Если b = 3 (mod 4), то b^c = 3, если c четно, и b^c = 1, если c нечетно. Это дает нам b^c (mod 4) для любых b и c, которые затем дают нам a^b^c (mod 5), все в постоянное время.

Наконец, с помощью a^b^c = a (mod 2) мы можем использовать китайскую теорему о остатках, чтобы найти a^b^c (mod 10). Для этого требуется сопоставление между (x (mod 2), y (mod 5)) и z (mod 10). Теорема о китайском остатке только говорит нам, что это отображение биективно, оно не говорит нам, как его найти. Однако есть только 10 вариантов, поэтому это легко сделать на листе бумаги или с помощью небольшой программы. Когда мы найдем это отображение, мы просто сохраним его в массиве, и мы можем выполнить весь расчет в O (1).

Кстати, это будет реализация моего алгоритма в питоне:

# this table only needs to be calculated once 
# can also be hard-coded 
mod2mod5_to_mod10 = [[0 for i in range(5)] for j in range(2)] 
for i in range(10): 
    mod2mod5_to_mod10[i % 2][i % 5] = i 

[a,b,c] = [int(input()) for i in range(3)] 

if a % 5 == 0: 
    abcmod5 = 0 
else: 
    if b % 4 == 0 or b % 4 == 1: 
     bcmod4 = b % 4 
    elif b == 2: 
     if c == 1: 
      bcmod4 = 2 
     else: 
      bcmod4 = 0 
    else: 
     if c % 2 == 0: 
      bcmod4 = 1 
     else: 
      bcmod4 = 3 

    abcmod5 = ((a % 5)**bcmod4) % 5 

abcmod2 = a % 2 

abcmod10 = mod2mod5_to_mod10[abcmod2][abcmod5] 

print(abcmod10)