The last digit problem

[ankur12106037]

Question->http://www.spoj.com/problems/LASTDIG/ My solution is not accepted on Spoj because my solution is taking more than 700 bytes. But i m not getting how to reduce or shorten my code or what can be done to reduce the memory
usage to be less than 700 bytes.I also read somewhere that by removing spaces b/w the code source code memory will reduce but still after doing that my code is not accepted.Plz help
#include<iostream>
using namespace std;
int lastdigit(int a,long int b);
int main()
{
int t,a;
long int b;
cin>>t;
while(t--)
{
cin>>a>>b;
cout<<lastdigit(a,b)<<"\n";
}
return 0;
}
int lastdigit(int a,long int b)
{ if(b==0){return 1;}
if(a%10==0){return 0;} //for a=0,10,20
if(a%10==1){return 1;} //for a=1,11
if(a%10==5){return 5;} //for a=5,15
if(a%10==6){return 6;} //for a=6,16
int ret,mod=b%4;
if(a%10==2||a%10==8||a%10==4)//for a=2,12,8,18,4,14
{
if(a%10==8){if(mod==1){mod=3;}else if(mod==3){mod=1;}}
if(a%10==4){if(mod==1||mod==3){mod=2;}else if(mod==2){mod=0;}}
if(mod==1){ret= 2;}
else if(mod==2){ret =4;}
else if(mod==3){ret =8;}
else if(mod==0){ret= 6;}
}
else if(a%10==3||a%10==7||a%10==9)//for a=3,13,7,17,9,19
{
if(a%10==7){if(mod==1){mod=3;}else if(mod==3){mod=1;}}
if(a%10==9){if(mod==1||mod==3){mod=2;}else if(mod==2){mod=0;}}
if(mod==1){ret= 3;}
else if(mod==2){ret= 9;}
else if(mod==3){ret= 7;}
else if(mod==0){ret= 1;}
}

return ret;
}

[ne555]

You could simply change the algorithm
Using modular arithmetic (a*b) mod m = (a mod m * b mod m) mod m
And also use a dynamic approach for the power computation a^b = a^(b/2) * a^(b/2) * a^(b mod 2)

[ankur12106037]

I don't exactly get your modular arithmetic step .Can u please explain it further.
But the dynamic approach for power computation u suggested is really good as it takes only O(logn) time and i think that approach will surely help.

[ne555]

You need to apply modulo 10 to the power
(a^b) mod 10 = ( a^(b/2) * a^(b/2) * a^(b mod 2) ) mod 10

In this case 'a' is quite small, and computing its square shouldn't bring any issue. But in the general case you may need to distribute that module so it doesn't overflow
(a^(b/2) mod 10 * a^(b/2) mod 10 * a mod 10) mod 10