НГУ

Форумы НГУ
Текущее время: Пн авг 19, 2019 2:00 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: помгите с решением
СообщениеДобавлено: Пн окт 09, 2006 2:49 am 
Не в сети
Редкий гость

Зарегистрирован: Пн окт 09, 2006 2:47 am
Сообщения: 1
помогите найти алгоритм решения ниже указанной задачи или посоветуйте в какую сторону копать:

дана функция f(x) = x/(sqrt(N - x))

найти такое множество Х (только целочисленные положительные), при котором f(x) принимает целочисленные положительные значения:

пытался решать через такую замену: x=N - k^2, огда задача сводится к:
f(k)=N/k - k, т.е. достаточно разложить N на простые множители, но так как в условии N очень большие (50-значное и больше), то эта замена пользы не приносит.

Может есть у кого идеи? устроят и численные методы!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: помгите с решением
СообщениеДобавлено: Пт окт 20, 2006 5:26 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
DaBEAT писал(а):
пытался решать через такую замену: x=N - k^2, огда задача сводится к:
f(k)=N/k - k, т.е. достаточно разложить N на простые множители, но так как в условии N очень большие (50-значное и больше), то эта замена пользы не приносит.


Увы, но без факторизации N здесь не обойтись. Дело в том, что если вы тем или иным способом найдете x такое, что x/sqrt(N-x) является целым, то число sqrt(N-x) будет делителем числа N. Другими словами, если вы сумеете определить искомые x быстрее чем факторизуя N, то это будет означать, что вы нашли новый более быстрый алгоритм факторизации (что крайне маловероятно).

Кстати, 50-значные числа (и даже 100-значные) не представляют особой проблемы для современных алгоритмов факторизации. Для примера можете попробовать факторизовать конкретное, используя этот ява-апплет, реализующий алгоритм факторизации ECM.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB