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.