If you are coding with Java, use BigIntegers

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