This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

To simplify a fraction you find the greatest common denominator (GCD) and divide both the numerator and the denominator by it.

Iterating through the smaller number is sufficient for the problem for \mathcal{O}(\sqrt{min(N, D)})

However a faster algorithm is using Euclid’s algorithm for GCD.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);

Time complexity

\mathcal{O}(\log min(N, D))


Read the problem.