題意を満たすような数列はファレイ数列と呼ばれます.

このとき,ファレイ数列のある項\(\frac{u}{v}\)が与えられた時,その隣接項を\(O(logM)\)で求めることが可能です.

ファレイ数列において成り立つ以下の性質を応用します.

・\(\frac{x_i}{y_i},\frac{x_{i + 1}}{y_{i + 1}}\)をファレイ数列の隣接する\(2\)項とするとき

\(x_{i + 1} y_i - x_i y_{i + 1} = 1 ・・・ (※)\)

が成立する.

今,我々にとって既知の値は\((x_{i},y_{i})\)であり,未知の値は\((x_{i + 1},y_{i + 1})\)であるとします.

\(gcd(x_i,y_i) | 1\)より,方程式\((※)\)には解が存在し,ユークリッドの互助法の原理で特殊解\((x_{i + 1},y_{i + 1}) = (h,k)\)を\(1\)つ求めます.

すると\((※)\)の一般解は,\(t\)を任意の整数として

\((x_{i + 1},y_{i + 1}) = (h + x_i t,k + y_i t)\)と書き表せます.

\(\frac{x_i}{y_i} < \frac{h + x_i t}{k + y_i t}\)

は\({k + y_i t} > 0\)ならば常に成り立ち\(\frac{h + x_i t}{k + y_i t}\)は\(t\)に対して単調減少します.

よって,\(\frac{x_i}{y_i}\)より大きく,できるだけそれに近い値を与える\(t\),すなわち,分母が\(M\)を超えない範囲でできるだけ大きい\(t\)を与えれば良いです.

ファレイ数列の初項は\(\frac{1}{M}\)ですので,ここから\(K\)項まで上記のアルゴリズムにより計算し,\(K\)番目の項を\(O(KlogM)\)で求めることができます.

[Pythonでの実装例]

M, K = map(int, input().split())
p, q = 1, M
for i in range(K - 1):
    x = pow(q, - 1, p)
    y = (q*x-1)//p
    s = (M-y)//q
    p,q = x+s*p, y+s*q
if p < q:
    print(p, q)
else:
    print(-1)