Подсчет пар из первых N натуральных чисел с остатком не менее K

Даны два положительных целых числа N и K , задача состоит в том, чтобы найти количество пар (a, b) в диапазоне [1, N] таких, что a%b равно как минимум K .

Примеры:

Input: N = 5, K = 2
Output: 7
Explanation: 
Following are the all possible pairs satisfying the given criteria:

1. (2, 3): The value of 2%3 = 2(>= K).
2. (5, 3): The value of 5%3 = 2(>= K).
3. (2, 4): The value of 2%4 = 2(>= K).
4. (3, 4): The value of 3%4 = 3(>= K).
5. (2, 5): The value of 2%5 = 2(>= K).
6. (3, 5): The value of 3%5 = 3(>= K).
7. (4, 5): The value of 4%5 = 4(>= K).

Therefore, the total count of pairs is 7.

Input: N = 6, K = 0
Output: 36

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные пары (a, b) в диапазоне [1, N] и, если значение a%b не меньше K , то подсчитать эту пару. После проверки всех пар выведите общее количество полученных пар.

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

Эффективный подход. Описанный выше подход также можно оптимизировать, перебирая диапазон [1, N] и фиксируя второе число в паре, т. е. b . Для каждого фиксированного b будет период N/b , и каждый период может быть объединен с (b – K) элементами. Таким образом, всего будет (N/b)*(b – K) элементов. Теперь для оставшихся элементов N%b будет max(0, n%b – k + 1) пар. Выполните следующие шаги, чтобы решить проблему:

• Если значение K равно 0 , то выведите N ² как результирующее количество допустимых пар.
• Инициализируйте переменную, скажем , как 0 , которая хранит результирующее количество пар.
• Переберите диапазон [K + 1, N], используя переменную b , и выполните следующие шаги:
  • Добавьте значение (N/b)*(b – K) к переменной ans .
  • Добавьте значение максимума (N % b – K + 1) или 0 к переменной ans .
• После выполнения вышеуказанных шагов выведите значение ans как результирующее количество пар.

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

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