Длинная арифметика: найти остаток от деления большого числа (до 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;

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

Новые блоги и статьи Все статьи Все блоги /
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .	Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. zorxor 22.08.2026 Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .	Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.	Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .

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

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