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 for gcd 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.

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))

别看下面几位大爷的瞎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).

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.

Farey sequence can be used to generate reduced proper fractions.