4 ms·
Yep, that's pretty much how I solved it too. I had (and still have) no idea how to apply the Chinese Remainder Theorem. Looking back at my solution, I just iter
by shever73 5y ago
Yep, that's pretty much how I solved it too. I had (and still have) no idea how to apply the Chinese Remainder Theorem. Looking back at my solution, I just iterated through the input, which I'd mapped to a Python list.
- Someone 5y agoNitpick: there’s no way to apply the Chinese Remainder Theorem. It merely states that “if one knows the remainders of the Euclidean division of an integer n by several integers, then one can* determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.”* (https://en.wikipedia.org/wiki/Chinese_remainder_theorem https://en.wikipedia.org/wiki/Chinese_remainder_theorem) It doesn’t say how to determine that number. https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Computation https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.
- anandoza 5y agoWell, you can apply the theorem to the problem. Or apply its principles to the problem.
- Someone 5y agoNo, you can’t. It only says the problem has a unique solution. It doesn’t even say an efficient algorithm for computing it exists, or even whether an algorithm exists. Neither of those are very hard to prove, but the theorem won’t help you there. For comparison, let’s say the “sorting theorem” says “if you have n different numbers, you can place them in a sequence so that no number is larger than its predecessor”. Now, you have two numbers. How do you apply that theorem to place them in a sequence so that no number is larger than its predecessor?