题解

思路

把 $N,M$ 看成一元二次方程 $x^2-Sx+P=0$ 的两个根。

做法

存在所求正整数对，当且仅当判别式 $D=S^2-4P$ 非负且为完全平方数，设 $D=r^2$ 后，$S-r$ 还是正偶数；此时 $N=(S-r)/2$、$M=(S+r)/2$ 就是满足条件的正整数。由于 $S^2$ 可达到 $10^{24}$，计算判别式及平方比较时必须使用 128 位整数。

在 $[0,S]$ 上二分求 $\lfloor\sqrt D\rfloor$，再精确检查平方、奇偶性和正数条件即可。

复杂度

时间复杂度为 $O(\log S)$，空间复杂度为 $O(1)$。