Подсчет пар целых чисел до X и Y, которые генерируют равные частное и остаток

Даны два целых числа X и Y , задача состоит в том, чтобы подсчитать количество пар (m, n) , таких что m / n = m % n и 1 ≤ m ≤ x и 1 ≤ n ≤ y .

Примеры:

Input: X = 4, Y = 5 
Output: 2 
Explanation: The pairs (3, 2) and (4, 3) satisfy the condition.

Input: X = 3, Y = 1 
Output : 0

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Чтобы условие выполнялось, числитель должен иметь вид (kn + k) . Следовательно, (kn + k)/n = (kn + k) % n = k.
• Это также означает, что k < n . Следовательно, k * k < k * n + k <= x. Следовательно, k < sqrt(x) .
• Следовательно, достаточно выполнить итерацию от 1 до sqrt(x) для числителя.
• Переписав k * n + k ≤ x , мы получаем n <= (x / k – 1) . Кроме того, n > k и n <= y из ограничений.
• Для каждого возможного значения числителя подсчитайте возможные значения знаменателя и обновите общее количество.

Ниже приведена реализация описанного выше подхода.

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