Нумерация дробей

시간 제한2초메모리 제한1024 MB

요약
n이 10^18 이하로 주어질 때, 격자 i/j를 대각선 방향으로 세는 표준 순서에서 n번째 분수의 분자와 분모를 구한다.
난이도

보통10점 중 6점

유형
수학, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

Кролик очень сильно любит дроби. Особенно складывать их, умножать и сокращать. Именно поэтому ему недавно был подарен большой набор дробей.

Вчера Кролик прочитал статью в очень авторитетном математическом издании, в которой рассказывался способ нумерации дробей. Кролик очень любил порядок, и поэтому после прочтения этой статьи он сразу понял, что нужно упорядочить подаренные ему дроби именно так.

Чтобы упорядочить дроби необходимо их положить в таблицу, как показано на рисунке. В строку с номером ii этой матрицы по порядку записаны дроби с числителем ii, а в столбец с номером jj дроби с знаменателем jj.

(1112→13… ↓↗↙↗ 212223… ↙↗↙ 313233… ↓↗↙ ⋮⋮⋮⋱ )\left(\begin{array}{ccccccc} \frac{1}{1} & &\frac{1}{2} & \rightarrow & \frac{1}{3} && \ldots \\\ \downarrow & \nearrow && \swarrow && \nearrow\\\ \frac{2}{1} && \frac{2}{2} && \frac{2}{3} && \ldots \\\ &\swarrow &&\nearrow && \swarrow\\\ \frac{3}{1} && \frac{3}{2} && \frac{3}{3} && \ldots \\\ \downarrow &\nearrow &&\swarrow &&\\\ \vdots && \vdots && \vdots && \ddots \\\ \end{array}\right)

Дальше необходимо выписать все дроби в том порядке, как показано на рисунке стрелками. Получится такая последовательность: 11\frac{1}{1}, 21\frac{2}{1}, 12\frac{1}{2}, 13\frac{1}{3}, 22\frac{2}{2}, 31\frac{3}{1}, …\ldots

Кролик проделал все эти операции и получил последовательность дробей, как и было описано в прочитанной им статье.

Сегодня к Кролику в гости пришел Винни-Пух. Ему тоже очень понравились дроби, особенно его удивила последовательность, в которой они расположены. Он захотел узнать, какая дробь стоит на позиции nn в этом порядке.

Вам требуется по числу nn найти числитель и знаменатель nn-ой дроби.

입력

Во входном файле дано число nn (1≤n≤10181 \le n \le 10^{18}) --- порядковый номер дроби в последовательности Кролика.

출력

В выходной файл требуется вывести через символ <</>> два числа: числитель и знаменатель соответствующей дроби.

예제3

  1. 예제 1

    입력
    1
    
    예상 출력
    1/1
    
  2. 예제 2

    입력
    6
    
    예상 출력
    3/1
    
  3. 예제 3

    입력
    2
    
    예상 출력
    2/1