Подсчитайте числа меньше N, модуль которых с A равен B

Даны три неотрицательных целых числа A , B и N , где A не равно нулю , задача состоит в том, чтобы найти количество целых чисел, меньших или равных N , модуль которых с A дает значение B.

Примеры:

Input: A = 6, B = 3, N = 15
Output: 3
Explanation: The numbers 3, 9 and 15 are less than or equal to N (= 15) and their modulo with A (= 6) is equal to B (= 3). Therefore, the count such numbers is 3.

Input: A = 4, B = 1, C = 8
Output: 2

Подход: Данная проблема может быть решена с помощью наблюдения, основанного на математике. Выполните следующие шаги, чтобы решить проблему:

• Если значение B не меньше A , то выведите 0 , так как не может быть таких чисел, модуль которых с A дает значение B .
• В противном случае, если значение B равно 0 , затем выведите значение C / A как количество таких чисел, модуль которых с A дает значение B .
• В противном случае выполните следующие действия:
  • Инициализируйте переменную, скажем, ans, с минимальным значением C/A .
  • Если значение (ans * A + B) меньше или равно N , то увеличьте значение ans на 1 .
  • После выполнения вышеуказанных шагов выведите значение ans как количество таких чисел, модуль которых с A дает значение B .

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

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