ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1814. Цепная дробь

Is complicated and sophisticated number theory algorithms are involved?
Послано caoyuan9642 31 янв 2011 21:23
I thought the algo is to find the loop of continued fraction.
But it seems that if the loop is too small, 10^9 would make this algo fail.

Give some hint plz.
Re: Is complicated and sophisticated number theory algorithms are involved?
Послано caoyuan9642 31 янв 2011 21:26
for example:

Sqrt(2)=1+1/(2+1/(2+1/(2+1/......
=[1,2,2,2,2,2,2,2,2......]
the loop number is 1
so if k=10^9 ,
it can fail to calculate [1,2],[1,2,2],[1,2,2,2],[1,2,2,2,2]......
Re: Is complicated and sophisticated number theory algorithms are involved?
Послано caoyuan9642 1 фев 2011 12:46
Accepted now.
No very complicated number theory is needed.
All you need is the chapter about continued fraction in any copy of basic number theory.