Количество различных GCD путем добавления того же числа с заданными двумя целыми числами

Даны два положительных целых числа N и M. Задача состоит в том, чтобы найти количество различных НОД, которые можно получить, прибавив целое число K к N и M , где K ≥ 0 .

Примеры:

Input: N = 8, M = 4
Output: 3
Explanation: If K = 0, then GCD(8, 4) = 4, 
If K = 1, then GCD(9, 5) = 1, 
If K = 2, then GCD(10, 6) = 2

Input: N = 7, M = 10
Output: 2
Explanation: If K = 0, then GCD(7, 10) = 1, 
If K = 2, then GCD(9, 12) = 3

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

The maximum value of GCD formed after adding any value of K will be abs(N – M).
Other than the above result if any other GCD is formed, that will be a perfect divisor of abs(N – M).

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Найдите абсолютную разницу между N и M (скажем, X ).
• Найдите количество уникальных делителей X .
• Верните это значение в качестве требуемого ответа.

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

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