Task 83. Уравнение 2

Задача: дано натуральное число n. Также дано уравнение:

1 / n = (1 / x) + (1 / y).

Необходимо найти кол-во решений, представленных в натуральных числах.

Входные данные: n - натуральное число, где n < 10^9.

Вывод: кол-во решений, представленных в натуральных числах.

Пример:

n = 2;

Answer = 3.

Идея: преобразовываем исходное уравнение:

1/n = (1/x) + (1/y);

1/n = (x + y) / x*y;

x*y = n*(x + y);

(x - n)*(y -n) = n^2

Кол-во пар решений (x,y) равно кол-ву представления числа n^2 в виде произведения множителей. А это равно кол-ву делителей числа n^2.

Если n = p1^a1 * p2^a2 * ... * pk^ak, то кол-во его делителей равно

d(n) = (a1 + 1) * (a2 + 1) * ... * (ak + 1)

Подробнее про кол-во делителей вы можете посмотреть здесь:

В нашем случае, нужно найти значение d(n^2) = (2*a1 + 1) * (2*a2 + 1) * ... * (2*ak + 1)

Для ясности, рассмотрим пример: n = 12.

Т.к. 12 = 2^2 * 3, то получаем d(12^2) = (2*2 + 1) * (2*1 + 1) = 15

Число 12^2 можно разложить на множители как 4 * 36. Получим систему уравнений:

x - 12 = 4;

y - 12 = 36;

x = 16; y = 48; - одни из решений уравнения 1/12 = (1/16) + (1/48)

Реализация:

Тест:

Report Page