We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
In order to solve it we must have an efficient method of calculating prime factors of big numbers. Brent factorization is helpful here. The problem is actually about counting divisors for numbers of the form: s * p1^k1 * p2^k2
where GCD(s, p1) = 1 and GCD(s, p2) = 1. Caching is also necessary as we count divisors for the same numbers many times.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #157: Solving the diophantine equation 1/a +1/b = p/10^n
You are viewing a single comment's thread. Return to all comments →
In order to solve it we must have an efficient method of calculating prime factors of big numbers. Brent factorization is helpful here. The problem is actually about counting divisors for numbers of the form: s * p1^k1 * p2^k2 where GCD(s, p1) = 1 and GCD(s, p2) = 1. Caching is also necessary as we count divisors for the same numbers many times.