Большие числа.

12.12.2010, 02:19. Показов 1163. Ответов 0

Метки нет (Все метки)

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

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

Известно, что число 123^137 при делении на m = 1395667104275780136328137029621666356023 1023738282086142590083335180486617588964 51829091736021396841, дает в остатке 9482464648460806585590200727807516027602 4600593637457675385307253373428352147655 8512528028591507652.
Написать программу, которая находит целое число x такое, что x^137 при делении на то же m, дает в остатке 8538509553018661636892472425864712986226 1947265617564028946668983863534803883841 1985760314991260370. Программа должна работать не более 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х минут.

Подскажите если можете

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

12.12.2010, 02:19

Ответы с готовыми решениями:

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

12.12.2010, 02:19

Помогаю со студенческими работами здесь

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

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

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

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

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

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

Наверх