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

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

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

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

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

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

@Cortas · 06.02.2019, 19:06

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

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

Если нужно найти остаток от деления именно от 10^100'000 и более значений не имеется, то для этого даже калькулятор не нужен. 10 в любой степени кроме 1 и 0 дает в остатке от 12 4

@Михаиллллллл · 06.02.2019, 19:24

% - остаток от деления

C++ (Qt)

1 2	int a = 9752938579; int b = a%12;

@Irrialon · 06.02.2019, 19:26 **[ТС]**

Нет, найти остаток надо на любое число находящееся в границах от 0 до 10^100 000(1 и 100 000 нулей после, если что)

@Михаиллллллл · 06.02.2019, 19:37

sqrt - корень

C++ (Qt)

#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 минуту
Вместо а вводите любое число и так рассчитайте остаток

@Irrialon · 06.02.2019, 19:47 **[ТС]**

Сообщение от Михаиллллллл

sqrt - корень

C++ (Qt)

#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 раз более длинными в задаче на нахождение корня

@Михаиллллллл · 06.02.2019, 19:50

С задачей нахождения остатка используйте long long вместо int.
Проэксперементируйте также с корнем, может сработает.

@Irrialon · 06.02.2019, 19:54 **[ТС]**

Сообщение от Михаиллллллл

С задачей нахождения остатка используйте long long вместо int.
Проэксперементируйте также с корнем, может сработает.

Вы знаете как выглядит значок степени, знаете что такое степень числа? Понимаете что такое 10^2, 10^10? Чему равны эти числа? Вы проходили уже степенные показатели, или ещё не доучились до этого момента?)
10^2=100
10^10=10 000 000 000
10^99=1 000 000 000...

@Михаиллллллл · 06.02.2019, 20:01

а я и не заметил, тогда задача становится интересной

@Irrialon · 06.02.2019, 20:03 **[ТС]**

Сообщение от Михаиллллллл

Не, я с радостью про это забыл.
Пришлось вручную посчитать, 10 в 18 вас видимо устроит.
long long От -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807
типы данных

Я в условии сказал что мне нужно десять в стотысячной

@Михаиллллллл · 06.02.2019, 20:10

но в таком случае вы просто не можете записать это число в обычную переменную.
видимо это число нужно записывать в виде произведений двух long long
после посчитайте остаток каждого из двух long long
перемножаете остатки и уж их остаток должен быть искомым числом

@SerVal · 06.02.2019, 20:23

Irrialon, Вам надо воспользоваться библиотекой для больших чисел. После чего написать

C++

1	#include "BigInt.h"

И подставлять в формулы большие числа вместо маленьких.

C++

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

Как-то так.

@Irrialon · 06.02.2019, 20:31 **[ТС]**

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

Irrialon, Вам надо воспользоваться библиотекой для больших чисел. После чего написать

C++

1	#include "BigInt.h"

И подставлять в формулы большие числа вместо маленьких.

C++

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++

#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
А компилятор не поддерживает эти библиотеки!(

@SerVal · 06.02.2019, 20:36

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

cin >> N;

Забавно... Интересно, есть ли желающие вводить BigInteger?

А вообще-то, всё так. Просто у Вас такой библиотеки нетути.
*наверное и компика тоже. И Вы пользуетесь какой-нибудь online IDE.

@Irrialon · 06.02.2019, 20:51 **[ТС]**

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

Забавно... Интересно, есть ли желающие вводить BigInteger?

А вообще-то, всё так. Просто у Вас такой библиотеки нетути.
*наверное и компика тоже. И Вы пользуетесь какой-нибудь online IDE.

Я пользуюсь вижл студио, оно ругается на отстутсвие библиотеки(я криворокий, поэтому в данном случае предпологаю что просто неправильно настроил), на сайте для задач стоит GNU C++

@SerVal · 06.02.2019, 21:01

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

Я пользуюсь вижл студио, оно ругается на отстутсвие библиотеки(

И правильно ругается. Как ни настраивай, ничего не получится. Потому что в стандарте языка C больших чисел нетути.
И каждый тут выкручивается по-своему. Кто-то сам пишет, кто-то дёргает из Инета..
Я себе, ради интереса, написал(файл BigInt.h) и пользуюсь.(правда, работает медленно)

Croessmah · 06.02.2019, 21:10

Boost.Multiprecision?

C++

#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

@Irrialon · 06.02.2019, 21:47 **[ТС]**

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

Boost.Multiprecision?

C++

#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

Хм, выглядит очень неплохо, вот только придумать надо как работать с текстовым файлом(чтение входящего числа именно из него)

Croessmah · 06.02.2019, 22:10

C++

1 2	cpp_int num; file >> num;

Байт · 08.02.2019, 11:26

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

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

@SerVal 37 / 36 / 9 Регистрация: 16.04.2015 Сообщений: 283
	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 37 / 36 / 9 Регистрация: 16.04.2015 Сообщений: 283
	06.02.2019, 21:01	16
	Сообщение от Irrialon Я пользуюсь вижл студио, оно ругается на отстутсвие библиотеки( И правильно ругается. Как ни настраивай, ничего не получится. Потому что в стандарте языка C больших чисел нетути. И каждый тут выкручивается по-своему. Кто-то сам пишет, кто-то дёргает из Инета.. Я себе, ради интереса, написал(файл BigInt.h) и пользуюсь.(правда, работает медленно) 0

@Cortas 223 / 150 / 79 Регистрация: 14.03.2016 Сообщений: 459
	06.02.2019, 19:06	2
	Сообщение от Irrialon надо найти остаток от деления большого числа (до 10^100 000) на 12. Если нужно найти остаток от деления именно от 10^100'000 и более значений не имеется, то для этого даже калькулятор не нужен. 10 в любой степени кроме 1 и 0 дает в остатке от 12 4 0

@Irrialon 0 / 0 / 0 Регистрация: 06.01.2017 Сообщений: 13
	06.02.2019, 19:26 [ТС]	4
	Нет, найти остаток надо на любое число находящееся в границах от 0 до 10^100 000(1 и 100 000 нулей после, если что) 0

@Михаиллллллл 66 / 57 / 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

@Михаиллллллл 66 / 57 / 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

@Михаиллллллл 66 / 57 / 13 Регистрация: 16.03.2017 Сообщений: 426
	06.02.2019, 20:10	11
	но в таком случае вы просто не можете записать это число в обычную переменную. видимо это число нужно записывать в виде произведений двух long long после посчитайте остаток каждого из двух long long перемножаете остатки и уж их остаток должен быть искомым числом 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	08.02.2019, 11:26	20
	Irrialon, Как задаются числа? В виде строки цифр? Первая решается вообще чрезвычайно просто, без всякой длинки. Есть признаки деления на 3 и на 4 Вторую можно попробовать решить путем "школьного" алгоритма извлечения корня. Где-то обсуждалось недавно на форуме для обычных чисел. Попробую найти. И обобщить его для длинных. Добавлено через 3 минуты Разработать функцию, определяющую, является ли натуральное число квадратом какого-либо другого целого числа 1