Last digit problem in SPOJ looks simple but it contains a important concept of **Modular exponentiation. **If want AC in submission then you have to know about this concept ,to avoid time limit exceeded .

For example, given *b* = 5, *e* = 3, and *m* = 13, the solution, *c* = 8, is the remainder of dividing (125) by 13.

The** general method** is :

The most straightforward method of calculating a modular exponent is to calculate *b*^{e} directly, then to take this number modulo *m*. Consider trying to compute *c*, given *b* = 4, *e* = 13, and *m* = 497:

One could use a calculator to compute 4^{13}; this comes out to 67,108,864. Taking this value modulo 497, the answer *c* is determined to be 445.

Note that *b* is only one digit in length and that *e* is only two digits in length, but the value *b*^{e} is 8 digits in length.

In strong cryptography, *b* is often at least 256 binary digits (77 decimal digits). Consider *b* = 5 × 10^{76} and *e* = 17, both of which are perfectly reasonable values. In this example, *b*is 77 digits in length and *e* is 2 digits in length, but the value *b*^{e} is 1,304 decimal digits in length.This leadto time limit exceeded.

## Right-to-left binary method:

First convert e to it’s binary form:

, where the *length* of *e* is *n* bits. *a*_{i} can take the value 0 or 1 for any *i* such that 0 ≤ *i* < *n* – 1. By definition, *a*_{n – 1} = 1.

So now solution is :

The solution *c* is therefore:

**Now how will be your program approach :**

whileexponent > 0if(exponentmod2 == 1): result := (result * base)modmodulus exponent := exponent >> 1 base := (base * base)modmodulusreturnresult

So the function will be like this :

void lastdig{ scanf("%lld%lld",&n1,&n2); long long d=1; while(n2){ if(n2%2 !=0)//it can be 0 or 1 { d=(d*n1)%10; } n2 >>=1; n1=(n1*n1)%10; } printf("%lld\n",d); }

Hope you learnt something #HappyCoding. 🙂

Source : wikipedia.org