Сосчитайте тройки так, чтобы произведение двух чисел, сложенных с третьим числом, было N.

Для данного положительного целого числа N задача состоит в том, чтобы найти количество троек (A, B, C), где A , B , C — положительные целые числа, такие, что произведение двух чисел, сложенных с третьим числом, равно N , т. е . A * B + С = Н .

Примеры:

Input: N = 3
Output: 3
Explanation:
Following are the possible triplets satisfying the given criteria:

1. (1, 1, 2): The value of 1*1 + 2 = 3.
2. (1, 2, 1): The value of 1*2 + 1 = 3.
3. (2, 1, 1): The value of 2*1 + 1 = 3.

Therefore, the total count of such triplets is 3.

Input: N = 5
Output: 8

Подход: Данная задача может быть решена путем преобразования уравнения A * B + C = N в виде A * B = N – C. Теперь единственные возможные значения A и B , которые могут удовлетворять приведенному выше уравнению, — это делители N — C. Например, если значение N – C = 18 , имеющее 6 делителей, равных 1, 2, 3, 6, 9, 18. Таким образом, значения A, B, удовлетворяющие приведенному выше уравнению, равны: (1, 18), ( 2, 9), (3, 6), (6, 3), (9, 2), (18, 1) . Итак, при значении N – C = 18 возможные значения A , B равны 6 , т.е. количество делителей N – C(= 18) . Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте переменную, скажем, count как 0 , которая хранит общее количество возможных троек.
• Повторяем цикл по диапазону [1, N – 1], используя переменную i , и для каждого значения я нахожу общее количество делителей (N – i) и добавляю его к переменной count .
• После выполнения вышеуказанных шагов выведите значение count как результирующее количество троек.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*sqrt(N))
Вспомогательное пространство: O(1)