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

@ohio · Регистрация: 13.03.2025

Студворк — интернет-сервис помощи студентам

Длинный корень
(Время: 1 сек. Память: 16 Мб Сложность: 67%)
По заданному натуральному числу А требуется найти наибольшее число В такое, что B2 ≤ A.

Входные данные
Во входном файле INPUT.TXT записано натуральное число A (A ≤ 103000).

Выходные данные
В выходной файл OUTPUT.TXT выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей.

все до чего я смог дойти это вот:

Pascal
1
2
3
### var a:=ri;
var b:=sqrt(a);
write(b:0:0);

это последнее решение мое но оно не правильное, подскажите правильное и короткое решение пожалуйста
самое успешное решение прошло 10 тестов вот:

Pascal
1
2
3
4
5
6
7
var a:double;
begin
  read(a);
  a:=sqrt(a);
  a:=trunc(a);
  writeln(a);
end.

оно по времени не прошло, помогите как через метод ньютона писать такие задачки, или если существует решение в лоб то как в лоб можно?

@Cyborg Drone · 11.02.2026, 17:56

Сообщение от ohio

прошло 10 тестов вот

Следовательно, тесты поганые.

Сообщение от ohio

оно по времени не прошло

Нет, не по времени. Вам показалось.

Ваше равнодушие относительно создания темы:

Сообщение от ohio

B2 ≤ A

Вы хотели написать B² ≤ A, правильно?

Сообщение от ohio

A ≤ 103000

Вы хотели написать A ≤ 10³⁰⁰⁰, правильно?

Очевидно, что это задание с проверочного сайта. На любом проверочном сайте файловый ввод-вывод не обязателен, что подтверждается Вашими программами, которые сайт принял.

И Ваши эти программы... По-Вашему получается, что 10³⁰⁰⁰ может поместиться в integer или double? Вы заблуждаетесь, в integer помещается целое число не более 2147483647=2.147483647*10⁹ (значащих цифр не более 10), а в double помещается вещественное число не более 1.79769313486232*10³⁰⁸ (значащих цифр не более 15).

На самом деле, у Вас по заданию задача на длинную арифметику, причём на самописную длинную арифметику, о чём жирно так намекает фраза "Число B следует выводить без лидирующих нулей".

О чём Вы подумали, когда писали программы? Не отвечайте, не надо, это риторический вопрос.

К счастью, самопальной длинной арифметики делать не придётся, поскольку тема находится здесь. В Pascal ABC.NET есть целочисленный тип BigInteger, как раз подходящий для Вашей задачи.

Итак, говоря другими словами, Вам требуется вычислить целочисленный квадратный корень. Будем вычислять его, как Вы и советуете, методом Ньютона, он же метод касательных, он же метод Герона, он же вавилонский метод.

Итерационная формула для целочисленного квадратного корня:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> b_{k+1}=\lfloor \frac{b_k+\lfloor \frac{a}{b_k}\rfloor }{2}\rfloor<br />$

Программа в идиотском коротком стиле, как Вы любите:

Pascal
1
2
3
4
5
6
7
8
9
###
  var A := RBI;
  var B: BI;
  var t := A div 2;
  repeat
    B := t;
    t := (A div B + B) div 2
  until (t = B) or (t = B + 1);
  B.Pr

Программу можно укоротить (и несколько замедлить), если объявить переменные в виде кортежа.

Программу можно несколько ускорить, если задать лучшее начальное приближение, и исключить копирование BigInteger b := t. Я считаю, что Вам и так достаточно.

Если вдруг окажется, что требуется решение без BigInteger, пишите, напишу.

Решение "в лоб" обсуждать не станем. Сами знаете, почему.

Материалы по теме:
Википедия - Целочисленный квадратный корень
Википедия - Итерационная формула Герона
Википедия - Методы вычисления квадратных корней

Не по теме:

ohio, я же Вас просил: подходите к созданию тем внимательно. А то складывается ощущение, что Вам ответ и на фиг не нужен. Кроме того, у меня теперь есть стойкая уверенность, что Вы ничего делать не пытались вообще. Ну, кроме поиска, конечно.

И ещё. Фамилии, пожалуйста, не ленитесь писать с прописной буквы. Всё-таки, сэр Исаак Ньютон - уважаемый человек.

@ohio · 12.02.2026, 12:13 **[ТС]**

спасибо, всё учту. Как более рациональное решение сделать, на дурацком acmp.ru все равно выдает runtime error хотя в паскале все окей, я вводил довольно большие значения.И да, на счет вашего примечания что я не понимаю что integer и double маленькие скажу: я знаю это, просто или не написал или как, спасибо вам за помощь.

@Cyborg Drone · 12.02.2026, 18:14

Не знаю, что там роботу не нравится. У меня Pascal ABC.NET версия 3.8.3, у ацмп Pascal ABC.NET версия 3.11.0, у меня работает, у них - нет. Вероятно, это из-за каких-то условностей со вводом со стороны сайта. Попробуйте так:

Pascal
1
2
3
4
5
6
7
8
9
##
  var A := ReadlnBigInteger;
  var B: BigInteger;
  var t := A div 2;
  repeat
    B := t;
    t := (A div B + B) div 2
  until (t = B) or (t = B + 1);
  B.Println

Более рациональное решение - это всё же вряд ли, я не нашёл приемлемого выражения для начального приближения корня.

Версия без копирования BigInteger:

Pascal
1
2
3
4
5
6
7
8
9
10
11
##
  var A := ReadlnBigInteger;
  var B := A div 2;
  var B1 := 0bi;
  var f := false;
  repeat
    f := not f;
    if f then B1 := (A div B + B) div 2
    else B := (A div B1 + B1) div 2
  until abs(B1 - B) <= 1;
  if f then B1.Println else B.Println

@ohio · 18.02.2026, 10:05 **[ТС]**

Cyborg Drone, извините но там конечно слишком большое число вводится что просто по времени не укладывается за 1 секунду сделать столько вычислений это бред, зачем вообще делать такие задачи?

Добавлено через 1 минуту
а да, задача так и называется на acmp.ru длинный корень скорее всего нужно найти приближение получше
ну или просто не решать мне такие сложные задачи

agvego5 · 18.02.2026, 14:37

Сообщение от ohio

acmp.ru длинный корень

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

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

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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@ohio 0 / 0 / 0 Регистрация: 13.03.2025 Сообщений: 29
	12.02.2026, 12:13 [ТС]
	спасибо, всё учту. Как более рациональное решение сделать, на дурацком acmp.ru все равно выдает runtime error хотя в паскале все окей, я вводил довольно большие значения.И да, на счет вашего примечания что я не понимаю что integer и double маленькие скажу: я знаю это, просто или не написал или как, спасибо вам за помощь. 0

@ohio 0 / 0 / 0 Регистрация: 13.03.2025 Сообщений: 29
	18.02.2026, 10:05 [ТС]
	Cyborg Drone, извините но там конечно слишком большое число вводится что просто по времени не укладывается за 1 секунду сделать столько вычислений это бред, зачем вообще делать такие задачи? Добавлено через 1 минуту а да, задача так и называется на acmp.ru длинный корень скорее всего нужно найти приближение получше ну или просто не решать мне такие сложные задачи 0