Assume there exists a non-negative integer \(z\) such that \(x^2-y=z^2\). We can transform the formula into \(x^2-z^2=(x+z)(x-z)=y\).

Let \(p=x+z,q=x-z\). Instead of counting pairs \(x,y\), we will count pairs of integers \(p,q\) that satisfy the following conditions:

• \(p \geq q\);
• \(x=(p+q)/2\) is an integer;
• \(1 \leq x=(p+q)/2 \leq N\);
• \(1 \leq y=pq \leq N\).

From these conditions, we first see that \(p\) and \(q\) are positive integers. Additionally, it follows from \(pq \leq N\) that \((p+q)/2 \leq N\).

Here, we can try all possible values for \(q\), because \(q \leq \sqrt{N}\). Once we decide the value for \(q\), \(p\) must satisfy \(q \leq p \leq N/q\) and \(p \equiv q \bmod 2\), and we can count such values for \(p\) in \(O(1)\) time.

Therefore, the whole problem can be solved in \(O(\sqrt{N})\) time.