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

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

Восстановить пароль Регистрация
 
mezir
0 / 0 / 0
Регистрация: 12.12.2010
Сообщений: 3
12.12.2010, 02:19     Большие числа. #1
Здравствуйте. Помогите найти оптимальный алгоритм решения задачи.

Известно, что число 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     Большие числа.
Посмотрите здесь:

Ввести с клавиатуры 10 чисел. Если среди них есть числа большие 15, заменить их на 15. Напечатать все полученные числа. C++
C++ упорядочить по возростанию числа большие 2
Большие числа C++
C++ Большие числа в C
C++ большие числа
C++ Ввести с клавиатуры 10 чисел. Если среди них есть числа, большие 15, заменить их на 15. Напечатать все полученные числа
Очень большие числа: узнать, есть ли остаток от деления одного числа на другое C++
Выводятся большие отрицательные числа C++

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

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

Текущее время: 15:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru