НГУ
http://forum.nsu.ru/

помгите с решением
http://forum.nsu.ru/viewtopic.php?f=24&t=14360
Страница 1 из 1

Автор:  DaBEAT [ Пн окт 09, 2006 2:49 am ]
Заголовок сообщения:  помгите с решением

помогите найти алгоритм решения ниже указанной задачи или посоветуйте в какую сторону копать:

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

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

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

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

Автор:  maxal [ Пт окт 20, 2006 5:26 am ]
Заголовок сообщения:  Re: помгите с решением

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.

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/