Project Euler #71: Ordered fractions

  • + 0 comments

    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}");
        }
    }
    

    }