c++ - TLE for large inputs. How to run my code within the time limit? -

problem link-http://www.spoj.com/problems/lastdig/

summary-given 2 non negative integers , b, print last digit of a^b.

i tried using algorithm find modular exponentiation using less memory space(http://en.wikipedia.org/wiki/modular_exponentiation#memory-efficient_method) getting tle(time limit exceeding) error solution. changes should make run code in within 1 second? note 10 test cases need run within 1 second.

my solution:

#include<iostream> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib>  typedef long long ll;  using namespace std;   int me(ll a, ll b) {     ll c=1;     int e=0;      while(e<b)     {         c=(c*a)%10;         e++;     }      return c; }  int main() {     int t;     ll a, b;     vector <int> ldigit(31);      cin>>t;     for(int i=0;i<t;i++)     {         cin>>a>>b;          if(b>=99999)             ldigit[i]=me(a, b);         else         {             int temp=pow(a, b);             ldigit[i]=temp%10;         }     }      for(int i=0;i<t;i++)         cout<<ldigit[i]<<endl;      return 0; } 

the algorithm using slow large exponentiations. fast modular exponentiation considers bits in exponent, , needs o(lg(n)) multiplications/divisions whereas code needs o(n) multiplications. @ exponent of 1 billion difference 1 billion ~30. see right-to-left binary method.

the pseudocode wikipedia is

function modular_pow(base, exponent, modulus)     assert :: (modulus - 1) * (base mod modulus) not overflow base     result := 1     base := base mod modulus     while exponent > 0         if (exponent mod 2 == 1):            result := (result * base) mod modulus         exponent := exponent >> 1         base := (base * base) mod modulus     return result 

which in c becomes

int modular_pow(int base, int exponent, int modulus) {     int result = 1;     base = base % modulus;     while (exponent) {         if (exponent & 1) {             result = (result * base) % modulus;         }         exponent >>= 1;         base = base * base % modulus;     }     return result; } 

whereas code runs while loop 2 billion times exponents of 2 billion, code above runs loop ~32 times.