Длинная арифметика: найти остаток от деления большого числа (до 10^100 000) на 12

@Irrialon · Регистрация: 06.01.2017

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

Здравствуйте, вопрос по поводу задачки, хочу попытаться реализовать решение на плюсах, а не на питоне.
Суть такая: надо найти остаток от деления большого числа (до 10^100 000) на 12.

Также ещё одна задачка на ту же тему: надо найти корень из числа, не превышающее 10^500, если оно является полным квадратом, в обратном случае вывести -1.

Непонятно именно то, как реализовать работу с такими числами в С++, если предоставите код с коментариями-буду благодарен!

@Irrialon · 09.02.2019, 11:25 **[ТС]**

Сообщение от Байт

Irrialon, Как задаются числа? В виде строки цифр?
Первая решается вообще чрезвычайно просто, без всякой длинки. Есть признаки деления на 3 и на 4
Вторую можно попробовать решить путем "школьного" алгоритма извлечения корня. Где-то обсуждалось недавно на форуме для обычных чисел. Попробую найти. И обобщить его для длинных.

Добавлено через 3 минуты
Разработать функцию, определяющую, является ли натуральное число квадратом какого-либо другого целого числа

Число задается в виде документа "input.txt", текстовый файл с числом

Байт · 09.02.2019, 13:28

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

Число задается в виде документа "input.txt", текстовый файл с числом

То есть в виде строки из цифр? Так? То, что эта строка помещена в файл - дело уже десятое.
Первую-то задачу уже решили?

Добавлено через 15 минут
По поводу второй задачи могу предложить метод деления пополам, как наиболее просто реализуемый. Правда, здесь без длинки не обойтись. Но операций надо реализовать всего три. Сложение, умножение и деление на 2.
Кроме того можно еще проверить последнюю цифру. Если она равна 2, 3, 7, 8 то ответ получается мгновенно: -1. Что решает задачу в 40 процентах случаев.

@Irrialon · 09.02.2019, 14:25 **[ТС]**

Сообщение от Байт

То есть в виде строки из цифр? Так? То, что эта строка помещена в файл - дело уже десятое.
Первую-то задачу уже решили?

Добавлено через 15 минут
По поводу второй задачи могу предложить метод деления пополам, как наиболее просто реализуемый. Правда, здесь без длинки не обойтись. Но операций надо реализовать всего три. Сложение, умножение и деление на 2.
Кроме того можно еще проверить последнюю цифру. Если она равна 2, 3, 7, 8 то ответ получается мгновенно: -1. Что решает задачу в 40 процентах случаев.

По первой задаче я понял, но для деления на 3 нужна ведь сумма цифр, как же её найти? В переменную то не запишешь это число

Байт · 09.02.2019, 14:39

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

но для деления на 3 нужна ведь сумма цифр, как же её найти? В переменную то не запишешь это число

Каждая цифра не больше 9-ти. Делите по модулю 3

C++
1
2
3
4
char s[[100000]; // Это число
int sd = 0;
for(int i=0; s[i]; i++)
  sd = (sd + s[i] - '0')%3;

Да и просто число до мульона спокойно влезет

Новые блоги и статьи Все статьи Все блоги /
После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .

@Irrialon 0 / 0 / 0 Регистрация: 06.01.2017 Сообщений: 13

	Длинная арифметика: найти остаток от деления большого числа (до 10^100 000) на 12 06.02.2019, 18:54. Показов 7026. Ответов 23 Метки алгоритмы, арифметика, большие числа, задачи с++ (Все метки) Здравствуйте, вопрос по поводу задачки, хочу попытаться реализовать решение на плюсах, а не на питоне. Суть такая: надо найти остаток от деления большого числа (до 10^100 000) на 12. Также ещё одна задачка на ту же тему: надо найти корень из числа, не превышающее 10^500, если оно является полным квадратом, в обратном случае вывести -1. Непонятно именно то, как реализовать работу с такими числами в С++, если предоставите код с коментариями-буду благодарен! 0