Python には Fraction.limit_denominator() という, 分母が \(N\) 以下である近似有理数を求めるメソッドがあり, これを使うことで簡単に解くことができます.

from fractions import Fraction

r = Fraction(input())
N = int(input())

ans = (r - Fraction("1e-100")).limit_denominator(N)
print(*ans.as_integer_ratio())