直方体の3辺の長さをp, q, r(p < q < r)とすると、距離の自乗は
(p + q)2 + r2
なのでこれが平方数ならば最短経路が整数になります。直方体の数を求める最も簡単な方法はp, q, rを列挙することです。これはO(M3)かかります。これでは箸にも棒にもかからなそうですが、実際に組んでみるとそうでもないです。
解の探索に単純な二分探索ではなく、Mのとき直方体の個数はだいたいO(M2logM)くらいなので、2点がわかっていれば解を推定できます。実際には簡単のために、cMdと仮定して2点を通るように解を推定します。最初の方はとんでもなく大きいMになって計算量が莫大にならないように2倍に抑えます。これで8分でした。
