WA for Magic trick

Seeing a bit of cold response on the editorial page i am posting this as a question.

Problem:::[Magic trick][1]

Here’s my EDIT:

``````
[2] and its giving a WA and i am unable to figure it out why...

[1]: http://www.codechef.com/problems/MTRICK
[2]: http://www.codechef.com/viewsolution/3256318``````

You will get overflow here M[i+1]=pow(b,mul);
b can be as large as 10^18 and even raising it a power of 2 will cause long long (int64_t) to overflow

so any suggestions?

There are only 2 ways to solve the integer overflow problem:

1. Simplest one. Use a language like Python or Java with inbuilt support for large numbers.

2. Use the fast multiply method mentioned in the editorial.

Also i feel there is no need for you to reverse the array. Just maintain a start and end pointer to know the range in which you have to operate. This works because you only have to update elements from i…N so the elements from 1…i-1 have already been evaluated and no further operation will affect them in anyway as all operations are done on elements in the range i…N.This is also described in the editorial.

1 Like

Still getting wa http://www.codechef.com/viewsolution/3256318 changed the code

got an AC :)very important to use that method :)thanks

but i am not able to get the working of this function. It would be really appreciable if you explain it in detail…

``````long long multiple(long long a, long long b, long long c) // a * b % c
{
if (b == 0) {
return 0
}
long long ret = multiple(a, b >> 1, c)
ret = (ret + ret) % c
if (b & 1) {
ret = (ret + a) % c
}
return ret
}``````

@anonymousins I have tried to explain fast multiplication here. I think you will understand the function after reading it.

//