You can use bitwise hacks to do the multiplication without using a
long long:
int multiply(int x, int y){z=0; while(y!=0){z+=z;if(y&1)z+=x;y=y>>1;z=z
%P;} return z;}
But (((long long) x) * y) % P is less prone to mistakes, may actually
be slightly more efficient, and takes less time to code.
Of course, using a "no overflow" integer type like ordinary integers
in Haskell, Whitespace or Python (say) is even less prone to mistakes.
On 25 May 2010, at 23:24, mtsay <[email protected]> wrote:
I have the same problem and I disagree with this comment. I am modding
all values by 100003, however, there was one multiplication at a point
in the code that I overlooked. Given x, y < 100003, the product x * y
could potentially reach 10 ^ 10 and exceed the 32-bit unsigned integer
limit, which is just above 4 * 10 ^ 9. Hence, casting to 64 bit
integer is necessary.
On May 24, 7:51 am, Bharath Balakrishnan <[email protected]>
wrote:
Your output was modulo 100003. A carefully coded program with mod
(%) in the
right places would have worked with int itself. You don't need a
long.
On Sun, May 23, 2010 at 1:11 AM, bokertov <[email protected]> wrote:
I used "int" and it worked for the small case. But my output for the
large case was incorrect. Then I found out if I replace "int" by
"long
long", then it's correct! I lost 30 points because of this stupid
mistake, man!
The reason is that 10^5*10^5 = 10^10, which is bigger than the upper
bound ~ 2*10^9 of int.
I'll surely learn this lesson, and will avoid it in the future.
--
You received this message because you are subscribed to the Google
Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected]<google-code
%[email protected]>
.
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
--
Regards,
Bharath B
"When the going gets tough, the tough get going"
--
You received this message because you are subscribed to the Google
Groups "google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to [email protected]
.
For more options, visit this group athttp://groups.google.com/group/
google-code?hl=en.
--
You received this message because you are subscribed to the Google
Groups "google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to [email protected]
.
For more options, visit this group at http://groups.google.com/group/google-code?hl=en
.
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
