Problem Code: MYSARA
problem: MYSARA Problem - CodeChef
here’s my program: CodeChef: Practical coding for everyone
Problem Code: MYSARA
problem: MYSARA Problem - CodeChef
here’s my program: CodeChef: Practical coding for everyone
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 Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks
Thank you
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.
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.