ARC125 B Squares
$ x^2 - y = z^2とおく. ここでこの式を変形すると, $ (x + z)(x - z) = yとなればよいことがわかる. ここで, $ x + z = p, x - z = qとおくと,
1. $ pq = y
2. $ q \leq p
3. $ \frac{p + q}{2}が整数
4. $ 1 \leq \frac{p + q}{2} \leq N
5. $ 1 \leq pq \leq N
という5つの条件が成り立てばよいことがわかる. ここで, 2.より$ q \leq \sqrt Nであるので, $ qを全探索してみる.
すると, 条件より$ q \leq p \leq \frac{N}{q}かつ$ p \equiv q(mod $ 2)なる$ pの個数を数えればよくなり, これは$ O(1)で求められる.
よって, $ O(\sqrt N)でこの問題を解くことができた.