https://www.codechef.com/viewsolution/36838098
I was just trying to pass the subtask with 10 points, but I failed, why?
1 Like
did you apply mod at the final result of pow1?
1 Like
Do you know what is the maximum value of n? I am asking you this because you have used pow function to calculate pow(2,i) where i is as high as n (5e5). So its causing wrong answer as you are requesting to calculate pow(2,500000).
Try to use modular exponentiation to calculate powers modulo any number.
2 Likes
Instead of inbuilt modulo method fmod() [it takes modulo at end of computation of power] , use your own method for power function which takes modulo at every step of overflow , i.e.
LL is for `long long int’
LL power_mod(LL a, LL k) {
if (k == 0)
return 1;
LL temp = power(a, k/2);
LL res;
res = ( ( temp % P ) * (temp % P) ) % P;
if (k % 2 == 1)
res = ((a % P) * (res % P)) % P;
return res;
}
2 Likes
thank you all, got it i checked till n=1000,
1 Like