We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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}");
}
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #71: Ordered fractions
You are viewing a single comment's thread. Return to all 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); } }
}