Решение уравнения. Подсчет (х, у)

Question

У меня проблемы с математикой:

Предположим, что у нас есть функция: F (x, y) = P; И мой вопрос: что было бы наиболее эффективным способом подсчета подходящих (x, y) графиков для этой функции? Это означает, что мне не нужны сами координаты, но мне нужно число из них. P находится в диапазоне: [0; 10 ^ 14]. «х» и «у» являются целыми числами. Это решается с помощью bruteforce или есть некоторые продвинутые приемы (математика / язык программирования (C, C ++)), чтобы решить это достаточно быстро?

Чтобы быть более конкретным, функция имеет вид: x * y - ((x + y) / 2) + 1.

Answer 1

x*y - ((x+y)/2) + 1 == P эквивалентно (2x-1)(2y-1) == (4P-3).

Итак, вы в основном ищете число факторизаций 4P-3.Как факторизовать число в C или C ++, возможно, другой вопрос, но каждая факторизация приводит к решению исходного уравнения.[Правка: на самом деле два решения, так как если A*B == C, то, конечно, (-A)*(-B) == C также].

Что касается языков программирования C и C ++, просто убедитесь, что вы используете достаточно большой типсодержать 4 * 10^14.int не подойдет, поэтому попробуйте long long.

Answer 2

У вас есть двухпараметрическая функция, и вы хотите решить ее для заданной константы.

Это довольно большое поле в математике, и, вероятно, существуют десятки алгоритмов решения вашего уравнения.Одна ключевая идея, которую многие используют, заключается в том, что если вы найдете точку, где F<P, а затем точку F>P, то где-то между этими двумя точками, F должно равняться P.

Один из самых основных алгоритмов поиска корня (или нуля, который вы, конечно, можете преобразовать, взяв F '= FP) - это метод Ньютона .Я предлагаю вам начать с этого и ознакомиться с более продвинутыми алгоритмами.Это очень обширная область изучения, так что приятного чтения!

В Википедии есть список алгоритмов поиска корней , которые вы можете использовать в качестве отправной точки.