sがtで割り切れるから、
p = s / t
と置きます。そうすると元の式は、
m2 = pt3(u3 + p)
となります。
ここでt = 1 p = 1とすると、
m2 = u3 + 1
これは因数分解ができるので簡単に解が求められますが、こういうケースは稀なので考えません。
次に、t = 1, p = 2としてみましょう。
m2 = 2u3 + 4
右辺は偶数だから、m = 2m1とおいて、
2m12 = u3 + 2
u3の項も偶数になるから、u = 2u1とおいて、
m12 = 4u13 + 1
となります。m1は奇数だから、というのもできますが、そこまではしません。このように各係数のうちの2つに共通因子があればこの処理を進めていけます。なくなれば普通にuを振って平方数になるか調べます。
このような処理を再帰的に行うと平方数になる探索をする範囲が小さくなるので速くなります。
3sが0.6sになりました。