|
Длинный корень
(Время: 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
| |
