|
|
|
|
|
|
by penteract
906 days ago
|
|
|
It's possible to answer "find the minimum n such that n%a is in s1 and n%b is in s2, assuming a and b are coprime" in runtime around O(n1+log(n1)*n2) where n1 is the size of s1 and n2 is the size of s2. n1*n2 can get at least as big as a*b/8 without a naive linear search being guaranteed to be fast, so this roughly square roots the runtime of 'CRT on all pairs' if n1 is close to n2. Here's the code, sorry it's not as well commented as yours, and I haven't integrated it into a solution to day 8. https://github.com/penteract/adventofcode/blob/master/utils/... . For more than 2 moduli, the best I can think of is to separate them into 2 roughly equal parts, generate the full lists of allowed remainders for each part, then use this algorithm to combine the parts. There may be better things you can do here (and perhaps you can show that for large sets of allowed remainders across enough different moduli, the solutions are spread out evenly enough there's one you can find by naive linear search). Dealing with non-coprime moduli is left as an exercise to the reader :). |
|
|