Project Euler #71: Ordered fractions
Project Euler #71: Ordered fractions
+ 0 comments Floating point comparison is disastrous. Use algebraic comparison.
I followed the recommendation of others and looked up Stern-Brocot tree, Farey neighbours. However, even though I believe I've sufficiently implemented those approaches, it is still TLE #16-#20 in Python.
Farey neighbours seemed promising with an elegant expression like , but it somehow could not pass all test cases.
My latest implementation was even optimised with logarithms and extensively used continued fraction representation. When binary search along the Stern-Brocot tree was too slow for an input like
3 1000000000 1000000000000000
because of occasionally looking forgcd
to get mediants, I switched to first finding the continued fraction representation of the parent, and get the neighbour fraction from it (the parent itself or the left branch of it whichever applicable).I don't know where and how I could further improve my solution, consider it gives result for
3 1000000000 1000000000000000
in about 1 second.EDIT: One of the test inputs that requires more time:
100010627 100010633 1000000000000000
.EDIT 2: Got a very fast solution making use of the concept of Farey neighbours and modular inversion (implemented with Extended Euclidean Algorithm, which I just copied from somewhere else). It looks mythical to me that just with the property , we could get to the answer in a blink of an eye. Very useful when the denominator of input is large. As I know nothing about modular inversion, will definitely come back to it after some reading.
+ 0 comments Here is my solution. Super fast in python 3
def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m t = int(input()) for i in range(t): a, b, n = [int(x) for x in input().split()] inv_a = modinv(a, b) r = n % b d = r - inv_a if d < 0: d += b den = n - d num = (den * a - 1) // b print("{} {}".format(num, den))
+ 0 comments 别看下面几位大爷的瞎BB。
(b*N-1)/(N*X) is a fraction less than b/a. Take the k step continued fraction of the fraction and calculate the denominator of the fraction represented by the continued fraction. Use Binary Search for k in range(1,32).
+ 0 comments Accepted by using __int128_t in C++. (only for comparision)
bool is_less(int64_t x1, int64_t y1, int64_t x2, int64_t y2) { return (__int128_t)x1 * y2 < (__int128_t)x2 * y1; }
search the answer in continued fraction tree. floating point error will cause problem.
+ 0 comments Farey sequence can be used to generate reduced proper fractions.
Sort 13 Discussions, By:
Please Login in order to post a comment