6286. Загадочное уравнение

Маленький Вася очень любит уравнения. Однажды ему на глаза попалось уравнение x + y + xy = n. Вася захотел узнать количество пар целых неотрицательных чисел x и y, которые являются решениями этого уравнения.

Вход. Одно число n (0 ≤ n ≤ 10⁹).

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

Пример входа	Пример выхода
5	4

РЕШЕНИЕ

теория чисел

Анализ алгоритма

Запишем уравнение в виде

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

Количество его решений равно количеству делителей числа n + 1. Если d делитель n + 1, то одно из решений уравнения можно найти из системы

Если обозначить через d(n) количество делителей числа n, то ответом на задачу будет значение d(n + 1).

Пример

Пусть n = 5, рассмотрим уравнение x + y + xy = 5. Перепишем его в виде

(x + 1)(y + 1) = 6

Число 6 имеет d(6) = d(2¹ * 3¹) = 2 * 2 = 4 делителя (ими будут 1, 2, 3, 6). Для нахождения всех решений уравнения следует решить 4 системы уравнений:

, ,,

Решениями систем будут пары (x, y): (0, 5), (1, 2), (2, 1), (5, 0).

Реализация алгоритма

Функция CountDivisors вычисляет количество делителей числа n.

int CountDivisors(int n)

{

int c, i, res = 1;

for (i = 2; i * i <= n; i++)

{

if (n % i == 0)

{

c = 0;

while (n % i == 0) n /= i, c++;

res *= (c + 1);

}

}

if (n > 1) res *= 2;

return res;

}

Читаем входное значение n.

scanf("%d", &n);

Выводим количество делителей числа n + 1.

printf("%d\n", CountDivisors(n + 1));