Форум программистов, компьютерный форум CyberForum.ru

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

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

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

12.12.2010, 02:19. Просмотров 809. Ответов 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х минут.

Подскажите если можете
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2010, 02:19     Большие числа.
Посмотрите здесь:

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

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

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

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

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

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

Вывести на экран числа большие заданного N - C++
Задание.Вывести на экран числа большие заданного N. Вроде все работает, но выдает ответ всегда 10 ответов, даже при N=70. Выведет 9 раз 70...

Имеются ли в матрице элементы, большие некоторого числа d? - C++
Дан двумерный массив целых чисел. Для каждой строки выяснить: 1) Имеются ли в нем элементы больше некоторого числа d 2) Имеются ли в...

Как компактно отображать и хранить большие числа? - C++
Есть ли какой-нибудь общеупотребимый формат? Типа 3*(2^123456-1) Сейчас развлекаюсь с числами Мерсенна. Для них просто придумал &quot;М23&quot;,...

Найти числа, большие N и составленные из тех же цифр - C++
Вводится некоторое натуральное число N, состоящее не более чем из 10 различных цифр (первая цифра - не 0). Определить, сколько существует...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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