Раціональні числа з періодичними дробами

Будь-яке раціональне число можна записати у вигляді $p/q$, де $p$ та $q$ — цілі числа. Всі раціональні числа менші за $1$ (тобто ті, для яких p < q) можна записати у вигляді десяткового дробу, але це представлення може потребувати повторення деяких цифр. Наприклад, раціональне число $7/22$ має десяткове представлення $0.3181818\dots$ Тут пара цифр $1$ та $8$ повторюється нескінченно. Зазвичай ці повторювані цифри позначають горизонтальною рискою зверху.

Якщо задано десяткове представлення раціонального дробу (з позначенням повторюваних цифр, якщо потрібно), ми можемо визначити сам раціональний дріб (тобто записати його у вигляді $p/q$, де $p$ та $q$ — цілі числа), використовуючи наступний алгоритм.

Нехай після десяткової крапки йдуть $k$ неповторюваних цифр, а потім група з $j$ повторюваних цифр. У прикладі з $7/22$ маємо k=1 (для цифри $3$) і j=2 (для цифр $1$ та $8$). Щоб відновити оригінальне число $X$ ($7/22$), обчисліть чисельник і знаменник наступним чином:

Після обчислення чисельник буде таким:

Знаменник дорівнює 1000-10=990. Обчислені чисельник і знаменник завжди будуть цілими числами для заданих вхідних даних. Таким чином, ми записуємо результат як дріб $315/990$. Скоротивши дріб, отримаємо $7/22$, як і слід було очікувати.