Problem Code: MYSARA

problem: https://www.codechef.com/problems/MYSARA

here’s my program: https://www.codechef.com/viewsolution/30749301

Problem Code: MYSARA

problem: https://www.codechef.com/problems/MYSARA

here’s my program: https://www.codechef.com/viewsolution/30749301

I guess pow function can result in values much greater than **long long int**, so u need to implement a power function that mod values as well each time u multiply the values by 2.

Much like https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

Thank you

- It still won’t get accepted.

Here’s the link to new submission: https://www.codechef.com/viewsolution/30752873

Anyway, thanks for help.

Your power function is still wrong. It will overflow. You need to take %p at each step.

```
const ll p=1e9 + 7;
//rest of code
ll power( ll N, ll S ){
if( S < 0 ){
return 0;
}
ll result = 1;
while( S > 0 ){
if( S & 1 ){
result = result * N;
result%=p;
}
N *= N;
N%=p;
S >>= 1;
}
return result;
}
```

Then it will work.

https://www.codechef.com/viewsolution/30753465

error in power function : take mod with both result and N variable

when you set count = -1 then continue from there because if you don’t continue

count += __builtin_popcount(last); can make it non negative

Yes it worked. I noticed it in other’s coude too, but couldn’t understand it.

Can you please explain why is it necessary to mod it down at every step?

Also, thanks for hellp.

Anything above 2^64 will overflow. So if count was 70, you would be computing 2^70 which will most definitely overflow before you take %p. So to avoid that, we just take mod p at every step.

1 Like

I understood. Thank you for all your efforts. You also helped my friend a few days ago. We’re new at competitive programming. Thanks to everyones’s support.