Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Длинный корень

(Время: 1 сек. Память: 16 Мб Сложность: 67%)

Для начала найдем количество цифр в ответе. Покажем, что квадрат K-значного числа имеет либо 2*K-1, либо 2*K цифр. Действительно, квадрат наименьшего K-значного числа, т.е. числа 10K-1, равен 102K-2, т.е. имеет 2*K-1 цифру; квадрат наибольшего K-значного числа, т.е. числа 10K-1, равен 102K-2*10K+1, т.е. имеет 2*K цифр. Поскольку функция y=x2 монотонно возрастает для всех x>0(т.е. для любых x1,x2 > 0, таких что x1 < x2 выполнено x12 < x22), квадрат любого K-значного числа будет иметь либо 2*K-1, либо 2*K цифр. Следовательно, если число A из входного файла имеет N цифр, то корень из него будет иметь ровно (N+1) div 2 цифр.

Теперь, когда мы знаем количество цифр в числе, будем последовательно подбирать его цифры, начиная со старших. Пусть K старших цифр уже подобраны. Поставим на K+1 место самую большую цифру - 9, и будем уменьшать ее до тех пор, пока квадрат полученного таким образом числа (считая, что все цифры ответа, начиная с K+2 и до самой младшей равны 0) не станет меньше либо равен числу A из входного файла. Таким образом, мы подобрали K+1 цифру нашего числа. Продолжая этот процесс, получим ответ на поставленную задачу.

В изложенном решении используется операция умножения "длинных" чисел. Благодаря алгоритму умножения "в столбик" эта задача сводится к многократному умножению "длинных" чисел на "короткие" и сложению "длинных" чисел. Заметим, что эта операция легко выполняется в том случае, если одно из чисел является степенью 10, умноженной на "короткое" число. Тогда достаточно умножить "длинное" число на это короткое, а затем сдвинуть результат на нужное число позиций, что равносильно умножению числа на степень 10.

Пусть aK - число, полученное на K-м шаге нашего приближения, b - очередная цифра, умноженная на 10 в соответствующей степени. Тогда aK+12=(aK+b)2=aK2+2aKb+b2. В стоящей справа сумме все слагаемые, кроме первого, представляют собой частный случай перемножения "длинных" чисел, изложенный выше. А первое слагаемое уже было вычисленно на предыдущем шаге алгоритма.

Разбор задачи взят с сайта http://olympiads.ru


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru