Подсчитайте пару целых чисел (x, y), таких, что разность между квадратами x и y является полным квадратом

Дано целое число N. Задача состоит в том, чтобы найти количество пар целых чисел (x, y), меньших N и больших 1, таких, что x ² – y является квадратным числом или 0.

Пример:

Input: N = 3
Output: 2
Explanation:
The only possible valid pairs are (1, 1), (2, 3). Therefore, the count of such pairs is 2.

Input: N = 2
Output: 1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные пары целых чисел (x, y) в диапазоне [1, N], а затем проверить, что если значение (x ² – y) является идеальным квадратом или нет. Если окажется, что это правда , то посчитайте эту пару. Проверив все возможные, выведите общее полученное количество.

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

Эффективный подход . Вышеупомянутый подход также может быть оптимизирован следующим наблюдением:

x²-y is a square of a number, let’s say square of z. 
x² – y = z²  
x² – z² = y
( x + z ) * ( x – z ) = y

Now, let x + z = p and x – z = q
p * q = y 

Таким образом, задача сводится к подсчету пар p, q вместо x, y .
Теперь, поскольку y может быть только в диапазоне от 1 до N
Таким образом, p*q также будет в диапазоне от 1 до N. А поскольку p>=q (поскольку x+z >= xz ), q будет в диапазоне от 1 до √N, а p будет в диапазоне от 1 до N/кв .

Also p+q = 2*x, so x = (p+q)/2. 
Now, as x can have a max value of N, therefore 
(p+q)/2 <= N
p <= 2*N-q
 

Итак, максимальное значение p = min (2*N – q, N/q).
Теперь, зная диапазоны p & q, попробуйте все возможные значения p & q . И после фиксации все возможные возможные пары будут (l, q), где l находится в диапазоне от q до максимального значения p.
Таким образом, общее количество сформированных пар составляет (p – q + 1) , скажем, cnt .

Теперь, когда мы знаем, что p=x+z и q=xz, значит, и p , и q либо четны, либо нечетны. И на основании этого вывода, если q четно, общее количество допустимых пар равно cnt/2 (после удаления всех пар с четным значением p) , а если оно нечетное, то общее количество допустимых пар равно (cnt/2 + 1) .

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

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