| 21 Абдуматин и Абдуводжид, 11 августа 2020 г. 13:46:10 |
| Спасибо брату Ньютону за его метод.
|
|
|
| 22 Кайролла Кайырхан, 23 марта 2020 г. 16:13:22 |
| Сколько тестов у задачи ?
|
|
|
| 23 Зинов Вадим, 07 декабря 2019 г. 4:08:03 |
| Олег, Никак =) Можно быстрое преобразование фурье для перемножения многочленов привинтить, тогда NLogN будет, но с этим куда больше морок))
|
|
|
| 24 Чечулин Лев Олегович, 03 декабря 2019 г. 16:40:04 |
| Зинов Вадим А как у тебя получается длинные числа перемножать за линию?
|
|
|
| 25 Жданов Максим Андреевич, 29 марта 2019 г. 10:25:57 |
| Решил через алгоритм "длиннорукого квадратного корня", реализованного на питоне. 10 ** 3000 считает за 0.04 секунды
|
|
|
| 26 Яндулов Богдан, 20 июля 2018 г. 11:51:18 |
| Методом Ньютона за секунду можно получить корень из числа ~10^100 000.
|
|
|
| 27 Дещук Ярослав Александрович, 26 июня 2018 г. 11:05:43 |
А отрицательные числа присутствуют?
Цитата из условия "натуральное число".
|
|
|
| 28 Винк В В, 03 мая 2018 г. 6:00:16 |
| На моём стареньком ноутбуке работает ровно 1 секунду с числом, состоящем из 7500 девяток. С девятками работает дольше всего, то есть со случайным числом той же длины вероятно будет быстрей. Если в Яндекс поиске набрать "Оригинальный метод извлечения квадратного корня", то первая ссылка укажет на страницу с названием "Математика, которая мне нравится". Лунёв Антон Андреевич, 05 августа 2009 г. 22:49:06 здесь пишет, что его решение укладывается в тайм лимит даже для 50000-значных чисел. Интересно это действительно так?
|
|
|
| 29 Зинов Вадим, 28 апреля 2018 г. 16:59:35 |
| Почему бин поиск в лоб не может работать? 3000log2(10) * 6000 ~ 60 000 000 - валится Но, если за основание длинки брать 1e9 , то 3000log2(10) * 667 ~ 6 500 000, что уже укладывается в секунду
|
|
|
| 30 Винк В В, 26 апреля 2018 г. 14:28:54 |
Нашёл интересный метод вычисления квадратного корня вычитанием нечётных чисел. Реализовал на Си++. Время 0.092 сек. Пишут, что этот метод реализован в большинстве ЭВМ, так как он самый быстрый.
На какой длине числа из случайных цифр у Вас на компьютере он работает за 1 секунду? И ещё можно ключевые слова для поиска например в гугле или википедии?
|
|
|
| 31 Завгородний Михаил Сергеевич, 05 марта 2018 г. 18:09:44 |
| На питоне вообще изи
|
|
|
| 32 Камынин Иван Анатольевич, 08 мая 2017 г. 0:07:43 |
| Очень сложная задача, гораздо больше 67% !!! P.s ну это если решать без разбора !
|
|
|
| 33 Зубашев Степан, 12 августа 2016 г. 14:21:51 |
| Все задачи на длинную арифметику решал по принципу "как в тетради руками". С делением длинного на длинное уже возникла сложность. Бинарный поиск проблему решил (правда там есть ещё куда оптимизировать). С корнем возникла засада. Я не умею брать корни на бумаге. Оказывается математики умеют. Перенёс такой алгоритм (он оооочень странный, прямо магия :D) на длинную арифметику. AC. Макс. время 0.28sec. Думаю если оптимизировать, то можно легко до 0.05-0.15 уложиться. Т.к. слишком грубо.
|
|
|
| 34 Попов Максим Станиславович, 04 июня 2015 г. 16:31:43 |
| Поможет ли в Python 3 для решения задачи тип Decimal?
|
|
|
| 35 Павлов Михаил Валерьевич, 07 февраля 2014 г. 9:34:41 |
| Если решать по формуле " nx = (x + n / x) / 2 " то на java проходит менее чем за пол секунды. хотя это что-то долго для этого метода.
|
|
|
| 36 Сулайманбек Асылбекович Карабеков, 18 декабря 2013 г. 18:54:58 |
| Использовал метод Ньютона, сразу ACCEPTED!
|
|
|
| 37 Мамбетниязов Кутлымурат, 26 декабря 2012 г. 20:53:29 |
Почему не просто: writeln(round(sqrt(a))); ?
По вопросу видно, что не с той задачи вы начали :) Здесь длинная арифметика, почитайте об этом в разделе "Курс олимпиадника".
|
|
|
| 38 Глейх Андрей Артурович, 14 июля 2012 г. 10:50:24 |
Ка ни ущербна реализация длинной арифметики на Java но все таки она готовая к использованию. Метод Ньютона + длинная арифметика и ваши волосы будут мягкими и шелковистыми!
Это точно метод Ньютона, а не бинарный поиск?
|
|
|
| 39 Шантарин Владимир Викторович, 26 июня 2012 г. 22:30:50 |
| Ох я и намучался... за 0.984 сдал, прямо впритык :D
|
|
|
| 40 Шуршилов Артём Александрович, 19 июня 2012 г. 0:51:00 |
| Решая методом Ньютона(касательных) надо брать "улучшенный выбор начального приближения" и тогда будет ништяк)все таки не пойму решал вроде правильно выдавал ошибку с округлением TLE интересная штука...
|
|
|
