On Monday, April 15, 2019 at 1:55:23 PM UTC-5, kitchent wrote: > By the way, for the problem itself, my attempt was to try my luck with 12 > through 18, after the failure to pass test set 2 with [2, 3, 5, 7, 11, 13, > 17]. And it was a shock to me that it worked. I thought it was pure luck that > could fail with another try, but from the wording of the analysis, it seemed > to be legit. Is Chinese Remainder Theorem relevant here?
Yes, the Chinese remainder theorem still works if the moduli are not coprime, but the result is only unique modulo their least common multiple, instead of their product. Since LCM(12,13,14,15,16,17,18) = 1113840, this is enough to solve test set 2. (See https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Generalization_to_non-coprime_moduli) -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/eac14538-d90f-4a00-b4f6-72d60e797ad2%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
