Project Euler 531 - Chinese Leftovers

Official link:

Thought Process

Clearly, the Chinese Remainder Theorem will be involved in this problem, one difference is we need to account for non-coprime moduli. The CRT wiki contains a section on this, so I just implemented the given algorithm, in order to do this I had to implement the standard Extended Euclidean Algorithm to get the Bezout coefficients, I'm surprised I haven't had to do this yet.

Then, I just implemented my standard Totient Sieve so that I wouldn't have to recalculate phi values and ran through all the possible values with my new Generalized CRT algorithm.

All of these functions have been added to my mathematical Library mathslib

Interactive Code

Input 2 integers separated by a space (a, b)

Code will output f(n,m) for a ≤ n < m < b