using System;

public class Program { public static (int, int, int) Egcd(int a, int b) { if (a == 0) return (b, 0, 1); else { var (g, y, x) = Egcd(b % a, a); return (g, x - (b / a) * y, y); } }

public static int Modinv(int a, int m)
{
    var (g, x, y) = Egcd(a, m);
    if (g != 1)
        throw new Exception("modular inverse does not exist");
    else
        return x % m;
}

public static void Main()
{
    int t = int.Parse(Console.ReadLine());
    for (int i = 0; i < t; i++)
    {
        var inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int a = inputs[0];
        int b = inputs[1];
        int n = inputs[2];
        int inv_a = Modinv(a, b);
        int r = n % b;
        int d = r - inv_a;
        if (d < 0)
            d += b;
        int den = n - d;
        int num = (den * a - 1) / b;
        Console.WriteLine($"{num} {den}");
    }
}

}

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

Find my java solution here

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

For those who became interested in Stern-Borcot due to this problem, just a note that studying the repeated application of it's recursive formulae can lead to quick algorithms (including for this problem, no GCD or modular inverse required), and also useful approximations. For example, my computer cannot tell the difference between M_PIl (pi as an f64) and 8717442233 / 2774848045, but also 355/113 is probably "good enough" in many cases (too large by 0.0000085%).

A related tree is the Calkin-Wilf tree. I recommend the paper "Recounting the Rationals" for those intrigued by Stern-Brocot. It's a very short, accessible, and intersting paper.

https://www.math.upenn.edu/~wilf/website/recounting.pdf