100003 is nice looking, is easy to see that is close 10^5 and seems very prime-ish with a quick glance. And primes are good for modular arithmetic.
Carlos Guía On Tue, May 25, 2010 at 11:42 PM, Bharath Raghavendran <[email protected] > wrote: > why did google choose 100003 and not some nice looking number like 100000 ? > :P > > > On 26 May 2010 03:54, 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]> >> <google-code%[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]<google-code%[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]<google-code%[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]<google-code%[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.
