Getting TLE in spoj LASTDIG2

Hi,

I’m attemting to solve this problem SPOJ LASTDIG2
So far I have used modular exponentiation (recursive procedure), but I’m getting TLE.
Here’s my solution:

#include <bits/stdc++.h>
using namespace std;

int modExpo(int x, int n){
if(n==0){
    return 1;
}else if(n == 1){
    return x%10;
}else if(n&1){
    return (modExpo(x, 1) * modExpo(x, n-1)) % 10;
}else{
    int temp = modExpo(x, (n/2));
    return (temp * temp) % 10;
}
}

int main(){
int t;
long long b;
string s;
scanf("%d",&t);

while(t--){
    cin>>s;
    scanf("%lld", &b);
    int a = s[s.length()-1] - '0';
    printf("%d\n", modExpo(a,b));
}

return 0;
}

Can somebody tell my why I’m getting TLE when modular exponentiation is the right way to solve this?
I thought about memoizing the subproblems but I’m not sure about how many different subproblems (<x, n> pairs) can be there. So could not be sure about which data structure to use to store the subproblems.

Thanks!

Its weird why this is giving TLE, Just using modExpo(x,1)*modExpo(x,n/2)*modExpo(x,n/2) for odd n gives me AC. Which doesn’t really make it more efficient.

That worked! But its really weird as you said
Thanks!

Can you elaborate a bit? Didn’t understand how you arrived at that conclusion. Thanks!

There is a period for every number. and forget i told the last

1 Like