4e-fraction-enumeration.js

/*

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

Ограничение времени	2 секунды (фактическое использование на тестах – до 76ms)
Ограничение памяти	256Mb (фактическое использование на тестах – до 5.54Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Георг Кантор доказал, что множество всех рациональных чисел счетно (т.е. все рациональные числа можно пронумеровать).

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

Дальше необходимо выписать все дроби в том порядке, как показано на рисунке стрелками. Получится такая последовательность: 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, …

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

Формат ввода
Во входном файле дано число n (1 ≤ n ≤ 10^18) — порядковый номер дроби в последовательности.

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

Пример 1

Ввод
1

Вывод
1/1

Пример 2

Ввод
6

Вывод
3/1

Пример 3

Ввод
2

Вывод
2/1

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim();

const number = BigInt(input);

function checkTriangularNumber(sequenceNumber) {
    return sequenceNumber * (sequenceNumber + 1n) / 2n >= number;
}

let left = 0n;
let right = number;
let middle = 0n;

while (left < right) {
    middle = (left + right) / 2n;
    if (checkTriangularNumber(middle)) {
        right = middle;
    } else {
        left = middle + 1n;
    }
}

const diagonalSequenceNumber = left;

const prevNumber = (diagonalSequenceNumber - 1n) * ((diagonalSequenceNumber - 1n) + 1n) / 2n;
const nextNumber = diagonalSequenceNumber * (diagonalSequenceNumber + 1n) / 2n;

if (diagonalSequenceNumber % 2n === 0n) {
    numerator = nextNumber - number + 1n;
    denominator = number - prevNumber;
} else {
    numerator = number - prevNumber;
    denominator = nextNumber - number + 1n;
}

const result = `${numerator}/${denominator}`;

fs.writeFileSync('output.txt', `${result}`);