Предыдущая тема :: Следующая тема |
Автор |
Сообщение |
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
Здравствуйте! Собственно вот задача:
"Известно, что число 123^137 при делении на m = 13956671042757801363281370296216663 56023102373828208614259008333518048 661758896451829091736021396841, дает в остатке 94824646484608065855902007278075160 27602460059363745767538530725337342 83521476558512528028591507652.
Написать программу, которая находит целое число x такое, что x^137 при делении на то же m, дает в остатке 85385095530186616368924724258647129 86226194726561756402894666898386353 48038838411985760314991260370. Программа должна работать не более 2 минут на ПЭВМ. Число x сохранять в текстовый файл в десятичном виде. Можно пользоваться пакетами программ для работы с большими целыми числами сторонних производителей."
Я использовал теорему Эйлера, но факторизация m занимает много времени (использовались наиболее эффективные алгоритмы - квадратичное решето и решето числового поля).
Подскажите, пожалуйста, решение без использования факторизации. |
|
Вернуться к началу |
|
|
aen |
|
Гений |
|
Сообщения: 1076 |
|
|
|
|
Moscvi4,
Здесь, мое ИМХО, ты получишь только флуда на пару недель ЗАдача решена так и не будет. _________________
http://www.podari-zhizn.ru/ |
|
Вернуться к началу |
|
|
maxx |
|
Прижившийся |
|
Сообщения: 106 |
Откуда: г.Орёл |
|
|
|
Moscvi4 писал(а): | Я использовал теорему Эйлера, но факторизация m занимает много времени (использовались наиболее эффективные алгоритмы - квадратичное решето и решето числового поля).
Подскажите, пожалуйста, решение без использования факторизации. |
А это ты с кем щас разговаривал? |
|
Вернуться к началу |
|
|
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
aen,
Думаю не всё так плохо. Препод, который её выдал, сказал, что задача решается очень просто. |
|
Вернуться к началу |
|
|
is-pirate |
|
Член |
|
Сообщения: 574 |
|
|
|
|
На паскале задачка пишется за пару минут абсолютно нубовским способом)))))) |
|
Вернуться к началу |
|
|
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
is-pirate, продолжайте))) |
|
Вернуться к началу |
|
|
is-pirate |
|
Член |
|
Сообщения: 574 |
|
|
|
|
не буду - у меня завтра экзамен и мне не до написания программы. И кстати в интернете есть примеры подобных задач. |
|
Вернуться к началу |
|
|
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
Уже три недели пытаюсь решить, в интернете искал - ничего не нашёл, подкинь идейку хоть. |
|
Вернуться к началу |
|
|
Remington |
|
Сферический конь |
|
Сообщения: 7249 |
Откуда: я знаю? |
|
|
|
Я решал тройныйе интергралы в уме, но такую чушь не слушал ни разу... _________________ Нужно очень много дури, чтобы стать Раджой Кодури. © |
|
Вернуться к началу |
|
|
is-pirate |
|
Член |
|
Сообщения: 574 |
|
|
|
|
Moscvi4, пусти поиск Х через цикл, который будет завершаться при достижении поставленных условий. Цикл с х на ходе в 1 (т.е. с каждым повторением цикла х увеличиваешь на 1). все условия и константы тебе даны уже. А поискать можно в примерах к учебникам. |
|
Вернуться к началу |
|
|
Remington |
|
Сферический конь |
|
Сообщения: 7249 |
Откуда: я знаю? |
|
|
|
Вам задачи кибернаторы ставят? _________________ Нужно очень много дури, чтобы стать Раджой Кодури. © |
|
Вернуться к началу |
|
|
is-pirate |
|
Член |
|
Сообщения: 574 |
|
|
|
|
Кстати если хочешь быстро получить решение своей задачи - Ответы мэил.ру и Ответы Google тебе в помощь - там фанатов разных задач уйма |
|
Вернуться к началу |
|
|
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
Да, я пробовал решать твоим способом. Самый очевидный метод. Но проблема в том, что сам x порядка 10^99. Если даже перебирать по миллиарду х-ов в секунду, уйдёт больше миллиона лет.
Моё решение заключалось в том факте, что x^fi(m), где fi(m) - функция Эйлера, даёт при делении на m в остатке ровно 1. Дальше тривиальные преобразования и x найден. Этот алгоритм намного быстрее, но его слабое место в нахождении функции Эйлера. Чтобы её вычислить нужно разложить на простые множители число m, а так как оно немаленькое, то и времени требуется побольше чем 2 минуты - несколько часов.
Добавлено спустя 27 минут 2 секунды:
Remington, что за кибернаторы? |
|
Вернуться к началу |
|
|
michael |
|
Гений |
|
Сообщения: 822 |
|
|
|
|
Moscvi4 писал(а): | Чтобы её вычислить нужно разложить на простые множители число m, а так как оно немаленькое, то и времени требуется побольше чем 2 минуты - несколько часов. |
вот и вот?
но мне кажется подход "перебором в лоб" тут не сработает.
все, все забыл. всю математику! |
|
Вернуться к началу |
|
|
Moscvi4 |
|
Новичок |
|
Сообщения: 23 |
|
|
|
|
michael, Не понимаю к чему здесь тест на простоту.
Думаю вообще не стоит пытаться усовершенствовать этот подход, так как препод сказал: "...с чего вы вообще взяли, что m нужно факторизовать?". Возможно существует другой способ, как-то связанный с самими числами. |
|
Вернуться к началу |
|
|
|