Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
1

Длинная арифметика

06.02.2019, 18:54. Просмотров 626. Ответов 23

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


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

Непонятно именно то, как реализовать работу с такими числами в С++, если предоставите код с коментариями-буду благодарен!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2019, 18:54
Ответы с готовыми решениями:

Длинная арифметика
:senor: Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него...

Длинная арифметика
http://www.********/index.asp?main=task&id_task=103 Как решить эту задачу? С помощью чего, и в...

Длинная арифметика
Как сделать типы длинных чисел, например, знаковое 256-ти битное целое и 256-ти битное вещественное...

Длинная арифметика
нужен текст програмы на С, в которой был бы реализован алгоритм ввода-вывода длинного числа,...

Длинная арифметика
Вот условие задачи: Во время исследований, посвященных появлению жизни на планете Олимпия, учеными...

23
Cortas
130 / 106 / 64
Регистрация: 14.03.2016
Сообщений: 353
Завершенные тесты: 5
06.02.2019, 19:06 2
Цитата Сообщение от Irrialon Посмотреть сообщение
надо найти остаток от деления большого числа (до 10^100 000) на 12.
Если нужно найти остаток от деления именно от 10^100'000 и более значений не имеется, то для этого даже калькулятор не нужен. 10 в любой степени кроме 1 и 0 дает в остатке от 12 4
0
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
06.02.2019, 19:24 3
% - остаток от деления
C++ (Qt)
1
2
int a = 9752938579;
int b = a%12;
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 19:26  [ТС] 4
Нет, найти остаток надо на любое число находящееся в границах от 0 до 10^100 000(1 и 100 000 нулей после, если что)
0
06.02.2019, 19:26
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
06.02.2019, 19:37 5
sqrt - корень
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <math.h>
double a = 65436;
int s sqrt(a);
int z = a;
int koren;
if(z%s==0)
{
koren = s
}
else
{
koren= -1;
}
Добавлено через 1 минуту
Вместо а вводите любое число и так рассчитайте остаток
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 19:47  [ТС] 6
Цитата Сообщение от Михаиллллллл Посмотреть сообщение
sqrt - корень
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <math.h>
double a = 65436;
int s sqrt(a);
int z = a;
int koren;
if(z%s==0)
{
koren = s
}
else
{
koren= -1;
}
Добавлено через 1 минуту
Вместо а вводите любое число и так рассчитайте остаток
Нет, вы не поняли, тип данных дабл не будем поддерживать такое число! Ведь дабл имеет границы -9 223 372 036 854 775 808 / 9 223 372 036 854 775 807, то бишь примерно 9*10^18, а у меня числа могут быть в 5000 раз более длинными в задаче на нахождение остатка и в 26 раз более длинными в задаче на нахождение корня
0
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
06.02.2019, 19:50 7
С задачей нахождения остатка используйте long long вместо int.
Проэксперементируйте также с корнем, может сработает.
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 19:54  [ТС] 8
Цитата Сообщение от Михаиллллллл Посмотреть сообщение
С задачей нахождения остатка используйте long long вместо int.
Проэксперементируйте также с корнем, может сработает.
Вы знаете как выглядит значок степени, знаете что такое степень числа? Понимаете что такое 10^2, 10^10? Чему равны эти числа? Вы проходили уже степенные показатели, или ещё не доучились до этого момента?)
10^2=100
10^10=10 000 000 000
10^99=1 000 000 000...
0
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
06.02.2019, 20:01 9
а я и не заметил, тогда задача становится интересной
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 20:03  [ТС] 10
Цитата Сообщение от Михаиллллллл Посмотреть сообщение
Не, я с радостью про это забыл.
Пришлось вручную посчитать, 10 в 18 вас видимо устроит.
long long От -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807
типы данных
Я в условии сказал что мне нужно десять в стотысячной
0
Михаиллллллл
64 / 55 / 13
Регистрация: 16.03.2017
Сообщений: 426
06.02.2019, 20:10 11
но в таком случае вы просто не можете записать это число в обычную переменную.
видимо это число нужно записывать в виде произведений двух long long
после посчитайте остаток каждого из двух long long
перемножаете остатки и уж их остаток должен быть искомым числом
0
SerVal
28 / 27 / 9
Регистрация: 16.04.2015
Сообщений: 262
06.02.2019, 20:23 12
Irrialon, Вам надо воспользоваться библиотекой для больших чисел. После чего написать
C++
1
#include "BigInt.h"
И подставлять в формулы большие числа вместо маленьких.

C++
1
2
3
4
5
6
7
8
9
10
D:\>TestBigInt.exe -generate "10^500"
 
 Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz
 
 Generating number 10^500
 time : 0 sec.
 
 big integer : 100000000 ... 0
 number of decimal digits = 501
 number of segments       = 52
Как-то так.
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 20:31  [ТС] 13
Цитата Сообщение от SerVal Посмотреть сообщение
Irrialon, Вам надо воспользоваться библиотекой для больших чисел. После чего написать
C++
1
#include "BigInt.h"
И подставлять в формулы большие числа вместо маленьких.

C++
1
2
3
4
5
6
7
8
9
10
D:\>TestBigInt.exe -generate "10^500"
 
 Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz
 
 Generating number 10^500
 time : 0 sec.
 
 big integer : 100000000 ... 0
 number of decimal digits = 501
 number of segments       = 52
Как-то так.
То есть как я понимаю должно выглядеть примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <BigInt.h>
#include <cmath>
using namespace std;
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    big integer N, K;
        cin >> N;
        K = N % 12;
        cout << K;
        return 0;
}
Добавлено через 3 минуты
solution.source:1:10: fatal error: BigInt.h: No such file or directory
А компилятор не поддерживает эти библиотеки!(
0
SerVal
28 / 27 / 9
Регистрация: 16.04.2015
Сообщений: 262
06.02.2019, 20:36 14
Цитата Сообщение от Irrialon Посмотреть сообщение
cin >> N;
Забавно... Интересно, есть ли желающие вводить BigInteger?
А вообще-то, всё так. Просто у Вас такой библиотеки нетути.
*наверное и компика тоже. И Вы пользуетесь какой-нибудь online IDE.
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 20:51  [ТС] 15
Цитата Сообщение от SerVal Посмотреть сообщение
Забавно... Интересно, есть ли желающие вводить BigInteger?
А вообще-то, всё так. Просто у Вас такой библиотеки нетути.
*наверное и компика тоже. И Вы пользуетесь какой-нибудь online IDE.
Я пользуюсь вижл студио, оно ругается на отстутсвие библиотеки(я криворокий, поэтому в данном случае предпологаю что просто неправильно настроил), на сайте для задач стоит GNU C++
0
SerVal
28 / 27 / 9
Регистрация: 16.04.2015
Сообщений: 262
06.02.2019, 21:01 16
Цитата Сообщение от Irrialon Посмотреть сообщение
Я пользуюсь вижл студио, оно ругается на отстутсвие библиотеки(
И правильно ругается. Как ни настраивай, ничего не получится. Потому что в стандарте языка C больших чисел нетути.
И каждый тут выкручивается по-своему. Кто-то сам пишет, кто-то дёргает из Инета..
Я себе, ради интереса, написал(файл BigInt.h) и пользуюсь.(правда, работает медленно)
0
Croessmah
++Ͻ
15317 / 8690 / 1659
Регистрация: 27.09.2012
Сообщений: 21,416
Записей в блоге: 2
Завершенные тесты: 1
06.02.2019, 21:10 17
Boost.Multiprecision?
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/integer.hpp>
 
int main()
{   
    using namespace boost::multiprecision;
    std::cout << powm<cpp_int>(10, 100000, 12);//10 ^ 100 000 % 12
}
https://rextester.com/TUIK5897
0
Irrialon
0 / 0 / 0
Регистрация: 06.01.2017
Сообщений: 13
06.02.2019, 21:47  [ТС] 18
Цитата Сообщение от Croessmah Посмотреть сообщение
Boost.Multiprecision?
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/integer.hpp>
 
int main()
{   
    using namespace boost::multiprecision;
    std::cout << powm<cpp_int>(10, 100000, 12);//10 ^ 100 000 % 12
}
https://rextester.com/TUIK5897
Хм, выглядит очень неплохо, вот только придумать надо как работать с текстовым файлом(чтение входящего числа именно из него)
0
Croessmah
++Ͻ
15317 / 8690 / 1659
Регистрация: 27.09.2012
Сообщений: 21,416
Записей в блоге: 2
Завершенные тесты: 1
06.02.2019, 22:10 19
C++
1
2
cpp_int num;
file >> num;
0
Байт
Эксперт C
20451 / 12981 / 2728
Регистрация: 24.12.2010
Сообщений: 27,163
08.02.2019, 11:26 20
Irrialon, Как задаются числа? В виде строки цифр?
Первая решается вообще чрезвычайно просто, без всякой длинки. Есть признаки деления на 3 и на 4
Вторую можно попробовать решить путем "школьного" алгоритма извлечения корня. Где-то обсуждалось недавно на форуме для обычных чисел. Попробую найти. И обобщить его для длинных.

Добавлено через 3 минуты
Разработать функцию, определяющую, является ли натуральное число квадратом какого-либо другого целого числа
1
08.02.2019, 11:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2019, 11:26

Длинная арифметика
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти...

Длинная арифметика
Алгоритмы всех операций в принципе уже готовы (длина числа ограничивается только ресурсами ПК)....

длинная арифметика
Долгое время бьюсь как составить программу по этой теме в интернете искал нашел это for (int...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru