С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
mezir
0 / 0 / 0
Регистрация: 12.12.2010
Сообщений: 3
#1

Большие числа. - C++

12.12.2010, 02:19. Просмотров 821. Ответов 0
Метки нет (Все метки)

Здравствуйте. Помогите найти оптимальный алгоритм решения задачи.

Известно, что число 123^137 при делении на m = 1395667104275780136328137029621666356023102373828208614259008333518048661758896451829091736021396841, дает в остатке 948246464846080658559020072780751602760246005936374576753853072533734283521476558512528028591507652.
Написать программу, которая находит целое число x такое, что x^137 при делении на то же m, дает в остатке 853850955301866163689247242586471298622619472656175640289466689838635348038838411985760314991260370. Программа должна работать не более 2 минут на ПЭВМ.


Я использую библиотеку Arageli (http://www.arageli.org/) для работы с большими числами.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <arageli.hpp>
#include <iostream>
using namespace std;
using namespace Arageli;
int main()
{
    big_int m="1395667104275780136328137029621666356023102373828208614259008333518048661758896451829091736021396841";
    big_int r="948246464846080658559020072780751602760246005936374576753853072533734283521476558512528028591507652";
    big_int x;
    while (1)
    {
        x++;cout<<x<<endl;
if (power(x,137)%m==r)
{
    cout<<"Result:"<<x<<endl;
break;
}
    }
    getchar();
    return 0;
}
Программа быстро находит число 123.
Если ввести остаток от деления x^137 на m, и оставить работать программу на ночь, она успеет перебрать примерно 65 миллионов, но нужного x так и не найдет.
То есть нужен другой алгоритм, работающий менее 2х минут.

Подскажите если можете
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2010, 02:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Большие числа. (C++):

Очень большие числа: узнать, есть ли остаток от деления одного числа на другое - C++
Требуется узнать, есть ли остаток от деления одного числа на другое. Оба числа много больше int64, ~1000 символов и больше. Я попытался...

Ввести с клавиатуры 10 чисел. Если среди них есть числа, большие 15, заменить их на 15. Напечатать все полученные числа - C++
Ввести с клавиатуры 10 чисел. Если среди них есть числа, большие 15, заменить их на 15. Напечатать все полученные числа.

Ввести с клавиатуры 10 чисел. Если среди них есть числа большие 15, заменить их на 15. Напечатать все полученные числа. - C++
Помогите решить задачу в Turdo C++, там где используется printf scanf: Ввести с клавиатуры 10 чисел. Если среди них есть числа большие...

Большие числа в C - C++
можно ли в языке С работать с большими целыми? Существует ли некое подобие BigInteger C#?

Большие числа - C++
Здравствуйте. Как в С++ работать с большими числами (600851475143, например)? Честно гуглил, но там ничего толкового не нашел. ...

большие числа - C++
скажите пожалуйсто есть ли какая нибудь библиотека в си++ для работы с большими числами (до 10^18), если нет то может у кого класс...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2010, 02:19
Привет! Вот еще темы с ответами:

упорядочить по возростанию числа большие 2 - C++
упорядочить по возростанию числа больше 2 , а остальные оставить на своих же местах

Выводятся большие отрицательные числа - C++
В функции max двумерный массив переводится сначала в одномерный, при выводе одномерного массива вместо правильных элементов выводятся...

Strtol и слишком большие числа - C++
Если strtol скормить строчку со слишком большим числом, оно вернет LONG_MAX и установит errno в ERANGE. Вопрос - если strtol скормить...

Возведение в степень по модулю. Большие числа - C++
Всем привет. У меня есть пару способов возведения в степень по модулю, но с большими числами не работает.:( Требуется вычислить A^X mod...


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

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

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