I was submitting the solution for Round #362 Div2 Problem E :
http://mirror.codeforces.com/contest/697/problem/E
I got WA on Test#4 on this submission : http://mirror.codeforces.com/contest/697/submission/19150824 I had typecasted every possible places where I felt overflow could occur with long long. I submitted many times but it gave wrong answer with typecast.
Then I submitted using 1ll in multiplication instead of typecast in this submission and it got accepted: http://mirror.codeforces.com/contest/697/submission/19150943
My question is why does typecasting not work and what is the difference between typecasting and 1ll?? Also when to use which because many of the solutions I coded before used typecasts and it worked well on various judges including Codeforces until I encountered this case for the first time.
Auto comment: topic has been updated by iamstg (previous revision, new revision, compare).
You're only typecasting expressions that have been of type long long already (see http://mirror.codeforces.com/contest/697/submission/19151715). You don't need any of the casts.
Thanks,majk but why did typecasting provide WA.. I just added it due to extra safety..does unnecessary typecasting have side effects??
No, it doesn't. It took me a while to spot the crucial difference.
*and%have the same priority and associativity. This means that((x%M) * (z*z)%M)%Mis equivalent to(((x%M) * (z*z))%M)%M. In other words, you calculatex%Mand then multiply it withz*z. Since bothxandzcan be up to 10^9, the result is up to 10^27, hence, overflow occurs. Proper parentheses prevented that in Your second submission.Keep in mind that the priority only affects the result in case of overflow, mathematically, the result is the same.
Great Analysis..majk..thank you for the help
Waah Daga !