Главная Анкета Форум Галерея Поиск Обратная связь Добавить в избранное
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация   ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения  ВходВход 
Помогите, пожалуйста, студенту с задачкой.
На страницу 1, 2  След.
 
Начать новую тему   Ответить на тему    Список форумов NEXUS -> О жизни
Предыдущая тема :: Следующая тема  
Автор Сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 28 Дек 2010 01:13    Заголовок сообщения: Помогите, пожалуйста, студенту с задачкой. Ответить с цитатой

Здравствуйте! Собственно вот задача:

"Известно, что число 123^137 при делении на m = 13956671042757801363281370296216663 56023102373828208614259008333518048 661758896451829091736021396841, дает в остатке 94824646484608065855902007278075160 27602460059363745767538530725337342 83521476558512528028591507652.
Написать программу, которая находит целое число x такое, что x^137 при делении на то же m, дает в остатке 85385095530186616368924724258647129 86226194726561756402894666898386353 48038838411985760314991260370. Программа должна работать не более 2 минут на ПЭВМ. Число x сохранять в текстовый файл в десятичном виде. Можно пользоваться пакетами программ для работы с большими целыми числами сторонних производителей."

Я использовал теорему Эйлера, но факторизация m занимает много времени (использовались наиболее эффективные алгоритмы - квадратичное решето и решето числового поля).
Подскажите, пожалуйста, решение без использования факторизации.
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
aen
Гений
Гений
Сообщения: 1076
СообщениеДобавлено: 28 Дек 2010 09:33    Заголовок сообщения: Ответить с цитатой

Moscvi4,
Здесь, мое ИМХО, ты получишь только флуда на пару недель Smile ЗАдача решена так и не будет.

_________________

http://www.podari-zhizn.ru/
Вернуться к началу
aen отсутствует Посмотреть профиль Отправить личное сообщение
maxx
Прижившийся
Прижившийся
Сообщения: 106
Откуда: г.Орёл
СообщениеДобавлено: 28 Дек 2010 14:20    Заголовок сообщения: Re: Помогите, пожалуйста, студенту с задачкой. Ответить с цитатой

Moscvi4 писал(а):
Я использовал теорему Эйлера, но факторизация m занимает много времени (использовались наиболее эффективные алгоритмы - квадратичное решето и решето числового поля).
Подскажите, пожалуйста, решение без использования факторизации.

А это ты с кем щас разговаривал?
Вернуться к началу
maxx отсутствует Посмотреть профиль Отправить личное сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 28 Дек 2010 16:31    Заголовок сообщения: Ответить с цитатой

aen,
Думаю не всё так плохо. Препод, который её выдал, сказал, что задача решается очень просто.
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
is-pirate
Член
Член
Сообщения: 574
СообщениеДобавлено: 28 Дек 2010 18:48    Заголовок сообщения: Ответить с цитатой

На паскале задачка пишется за пару минут абсолютно нубовским способом))))))
Вернуться к началу
is-pirate отсутствует Посмотреть профиль Отправить личное сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 28 Дек 2010 19:42    Заголовок сообщения: Ответить с цитатой

is-pirate, продолжайте)))
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
is-pirate
Член
Член
Сообщения: 574
СообщениеДобавлено: 28 Дек 2010 23:00    Заголовок сообщения: Ответить с цитатой

не буду - у меня завтра экзамен и мне не до написания программы. И кстати в интернете есть примеры подобных задач.
Вернуться к началу
is-pirate отсутствует Посмотреть профиль Отправить личное сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 28 Дек 2010 23:10    Заголовок сообщения: Ответить с цитатой

Уже три недели пытаюсь решить, в интернете искал - ничего не нашёл, подкинь идейку хоть.
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
Remington
Сферический конь
Сферический коньСферический коньСферический коньСферический коньСферический конь
Сообщения: 7249
Откуда: я знаю?
СообщениеДобавлено: 28 Дек 2010 23:37    Заголовок сообщения: Ответить с цитатой

Я решал тройныйе интергралы в уме, но такую чушь не слушал ни разу...
_________________
Нужно очень много дури, чтобы стать Раджой Кодури. ©
Вернуться к началу
Remington отсутствует Посмотреть профиль Отправить личное сообщение
is-pirate
Член
Член
Сообщения: 574
СообщениеДобавлено: 28 Дек 2010 23:41    Заголовок сообщения: Ответить с цитатой

Moscvi4, пусти поиск Х через цикл, который будет завершаться при достижении поставленных условий. Цикл с х на ходе в 1 (т.е. с каждым повторением цикла х увеличиваешь на 1). все условия и константы тебе даны уже. А поискать можно в примерах к учебникам.
Вернуться к началу
is-pirate отсутствует Посмотреть профиль Отправить личное сообщение
Remington
Сферический конь
Сферический коньСферический коньСферический коньСферический коньСферический конь
Сообщения: 7249
Откуда: я знаю?
СообщениеДобавлено: 28 Дек 2010 23:42    Заголовок сообщения: Ответить с цитатой

Вам задачи кибернаторы ставят?
_________________
Нужно очень много дури, чтобы стать Раджой Кодури. ©
Вернуться к началу
Remington отсутствует Посмотреть профиль Отправить личное сообщение
is-pirate
Член
Член
Сообщения: 574
СообщениеДобавлено: 28 Дек 2010 23:45    Заголовок сообщения: Ответить с цитатой

Кстати если хочешь быстро получить решение своей задачи - Ответы мэил.ру и Ответы Google тебе в помощь - там фанатов разных задач уйма
Вернуться к началу
is-pirate отсутствует Посмотреть профиль Отправить личное сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 28 Дек 2010 23:51    Заголовок сообщения: Ответить с цитатой

Да, я пробовал решать твоим способом. Самый очевидный метод. Но проблема в том, что сам x порядка 10^99. Если даже перебирать по миллиарду х-ов в секунду, уйдёт больше миллиона лет.
Моё решение заключалось в том факте, что x^fi(m), где fi(m) - функция Эйлера, даёт при делении на m в остатке ровно 1. Дальше тривиальные преобразования и x найден. Этот алгоритм намного быстрее, но его слабое место в нахождении функции Эйлера. Чтобы её вычислить нужно разложить на простые множители число m, а так как оно немаленькое, то и времени требуется побольше чем 2 минуты - несколько часов.

Добавлено спустя 27 минут 2 секунды:

Remington, что за кибернаторы?
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
michael
Гений
Гений
Сообщения: 822
СообщениеДобавлено: 29 Дек 2010 00:39    Заголовок сообщения: Ответить с цитатой

Moscvi4 писал(а):
Чтобы её вычислить нужно разложить на простые множители число m, а так как оно немаленькое, то и времени требуется побольше чем 2 минуты - несколько часов.


вот и вот?

но мне кажется подход "перебором в лоб" тут не сработает.
все, все забыл. всю математику!
Вернуться к началу
michael отсутствует Посмотреть профиль Отправить личное сообщение
Moscvi4
Новичок
Новичок
Сообщения: 23
СообщениеДобавлено: 29 Дек 2010 01:18    Заголовок сообщения: Ответить с цитатой

michael, Не понимаю к чему здесь тест на простоту.
Думаю вообще не стоит пытаться усовершенствовать этот подход, так как препод сказал: "...с чего вы вообще взяли, что m нужно факторизовать?". Возможно существует другой способ, как-то связанный с самими числами.
Вернуться к началу
Moscvi4 отсутствует Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов NEXUS -> О жизни Часовой пояс: GMT + 3
На страницу 1, 2  След.
Страница 1 из 2

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете вкладывать файлы
Вы можете скачивать файлы