Busca divisores o paga lo que debes... al álgebra

El problema se deja modelar algebraicamente como $n^2+p^2q=m^2$. Es decir, como $p^2q=(m-n)(m+n)$. Entonces, $m-n$ es $1, p, p^2$, y correspondientemente $m+n$ es $p^2q, pq, q$. De esta manera, $n$ es $(p^2q-1)/2, (pq-p)/2, (q-p^2)/2$. Si, por ejemplo, $p=3, q=11$, las soluciones son $49, 15, 1$.