Calculating the last digit of a^b where a and b are very large numbers

I have to make code that calculates the last digit of \$a^b\$. Here, \$a\$ can have up to 1000 digits whereas \$b\$ can be from 0 to 915*1015. Now I calculated the last digit of a and raised that single digit number to the power b and that number's last digit will be the answer.

#include 
#include 
#include 
using namespace std;
unsigned long long int foo (unsigned long long int a,unsigned long long int b );
int main (void)
{
    int test;
    cin>>test;
    while ( test != 0 )
    {
        string a;
        cin>>a;
        unsigned long long int b;
        cin>>b;
        char c;
        int e;
        string::iterator it = a.end()-1;
        c = *it;
        e = c -48;
        if ( e == 0 && b == 0 )
            cout<<"0"<<"\n";
        else
        {
            unsigned long long modu  = foo(e,b);
            cout<<modu<<"\n";
            test--;
        }
    }
    return 0;
}

unsigned long long int foo (unsigned long long int a,unsigned long long int b )
{
    unsigned long long int ret;
    if ( b == 0 )
        return 1;
    if ( b % 2 == 0 )
    {
        ret = foo(a,b/2);
        ret = ret*ret;
    }
    else if ( b % 2 != 0 )
    {
        ret = foo(a,b/2);
        ret = ret*ret;
        ret = ret*a;
    }
    return ret%10;
}

However, I don't know why this shows WA on submitting it? Any corner cases that I might be missing?

Wrong answer

$$ everything^0 = 1 => 0^0 = 1$$

if ( e == 0 && b == 0 )
        cout<<"0"<<"\n";

Solution

Last digit relay only on last digit and you can not look at digits than goes before last one. As your power is up to \$10^{18}\$ you have to use modular binary power function.

Here is my solution:

#include 
#include 

typedef unsigned long long int ULLI;
typedef unsigned int UI;

UI bin_pow(UI a, ULLI n) {
    UI result = 1;
    while (n) {
        if (n & 1) {
            result = (result * a) % 10;
            n -= 1;
        } else {
            a = (a * a) % 10;
            n >>= 1;
        }
    }
    return result;
}

int main(int argc, char *argv[]) {
    int n;
    std::cin >> n;
    while (n--) {
        std::string a;
        ULLI b;
        std::cin >> a >> b;
        std::cout << bin_pow(a.back() - '0', b) << std::endl;
    }
}

C++11 std::string


Since C++11 std::basic_string had method .back() that returns last char in the string.


To do this with C++98 you can use .rbegin() iterator.

Solution with complexity \$O(1)\$

Previous code can be acceptable solution, but if it will still not be enough, try to set predefined array for length of circle when

$$ a^{length} mod(10) = a | a = [0 \ldots 9]$$

I'd write some Python script, lets take a look at the results:

(2, [2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8])
(3, [3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7])
(4, [4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4])
(5, [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5])
(6, [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6])
(7, [7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3])
(8, [8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2])
(9, [9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9])

What does it means? First number is the digit which was processed. Array is array of lower digits from previous equation. As you can see, there are not too many circles of repetitions.

Lets take a look at digit 2:

• with power of 1 we have \$2^1 mod(10)=2\$

• with power of 2 we have \$2^2 mod(10)=4\$

• with power of 3 we have \$2^3 mod(10)=8\$

• with power of 4 we have \$2^4 mod(10)=6\$

• with power of 5 we have \$2^5 mod(10)=2\$

that's it, we've got the circle for digit 2.

Also digits may be grouped by number of powers before lower digit will be repeated.

• 2, 3, 7, 8 repeated after 4 power operations

• 1, 5, 6 repeated after each power opetation

• 4, 9 repeated each 2nd power operation

const unsigned int predefined[10][4] = {
    {0},
    {1},
    {2,4,8,6},
    {3,9,7,1},
    {4,6},
    {5},
    {6,4},
    {7,9,3,1},
    {8,4,2,6},
    {9,1}
};

unsigned int bin_pow(const unsigned int& a, unsigned long long int n) {
    if (!n) return 1;

    switch(a) {
        case 0:
        case 1:
        case 5:
            return a;
        case 2:
        case 4:
        case 7:
        case 8:
            return predefined[a][n & 3];
        default:
            return predefined[a][n & 1];
    }
}

StackExchange Code Review Q#64565, answer score: 5