The last digit a ^ b ^ c

Question

I am stuck in this problem:

Given a, b and c are three positive integers (such that 1 <= a, b, c <= 10 ^ 9), you should find the last digit of the number a ^ b ^ c. "

What I initially thought was O (log n) algorithm to increase a at power n.

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

Obviously, basic math can help, for example, the "last digit":

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

Where n% 4 is the remainder of the division n / 4

In short, I tried to combine them, but I could not get better.

Some help would really be appreciated.

Answer 1

The problem is that b^c can be very large. Therefore, you want to reduce it before using standard modular exponentiation.

You may notice that a^(b^c) MOD 10 can have no more than 10 different values.

Due to the dove principle, there will be a number p such that for some r :

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

This means that for any 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 

For any n = s+r+q*p with s < p you have:

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

You can simply replace n= (b^c) in the previous equation.

You only calculate (b^cr) MOD p where p <= 10 , which is easy to do, and then calculate a^((b^cr) MOD p)*a^r MOD 10 .

Answer 2

As I mentioned in my comments, this really has little to do with smart algorithms. The problem can be completely reduced using some elementary number theory. This will give the O (1) algorithm.

The Chinese remainder theorem says that if we know a certain number x modulo 2 and modulo 5, we know that modulo 10. Thus, finding a ^ b ^ c modulo 10 can be reduced to finding a ^ b ^ c modulo 2 and a ^ b ^ c modulo 5. Little Fermat’s theorem says that for any prime p, if p does not divide a, then a ^ (p-1) = 1 (mod p), therefore a ^ n = a ^ (n mod (p-1)) (mod p). If p divides a, then obviously a ^ n = 0 (mod p) for any n> 0. Note that x ^ n = x (mod 2) for any n> 0, therefore a ^ b ^ c = a (mod 2).

It remains to find a ^ b ^ c mod 5, which reduces to finding b ^ c mod 4. Unfortunately, we cannot use either the Chinese remainder theorem or Fermat's theorem. However, mod 4 has only 4 possibilities for b, so we can test them separately. If we start with b = 0 (mod 4) or b = 1 (mod 4), then, of course, b ^ c = b (mod 4). If we have b = 2 (mod 4), then it is easy to see that b ^ c = 2 (mod 4) if c = 1 and b ^ c = 0 (mod 4) if c> 1. If b = 3 (mod 4), then b ^ c = 3 if c is even, and b ^ c = 1 if c is odd. This gives us b ^ c (mod 4) for any b and c, which then gives us a ^ b ^ c (mod 5), all in constant time.

Finally, with a ^ b ^ c = a (mod 2), we can use the Chinese remainder theorem to find a ^ b ^ c (mod 10). This requires a comparison between (x (mod 2), y (mod 5)) and z (mod 10). The Chinese remainder theorem only tells us that this mapping is bijective, it does not tell us how to find it. However, there are only 10 options, so this is easy to do on a piece of paper or using a small program. As soon as we find this mapping, we simply store it in an array, and we can perform the entire calculation in O (1).

By the way, this will be the implementation of my algorithm in python:

 # 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)