Длинная арифметика: найти остаток от деления большого числа (до 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 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .

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

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