公差をdとすると、x = y + d, z = y - dだから、
x2 - y2 - z2 = -y2 + 4dy = y(4d - y) = n
nを素因数分解して約数を生成します。その約数をd1としてd2 = n / d1とすると、
y = d1
4d - y = d2
4d = d1 + d2
だから、d1 + d2が4で割り切れてd1が4dより小さければよいわけです。このようなd1の個数を数えればよいです。
もう少し踏み込んで考えてみましょう。yの4の剰余で考えてみます。
y | 4d-y | n |
---|---|---|
0 | 0 | 0 |
1 | 3 | 3 |
2 | 2 | 0 |
3 | 1 | 3 |
nは必ず4で割って余り0か3です。4で割り切れるときを考えましょう。
2が2個の場合、例えば12の場合、1と12に分割するとダメですね。2と6はOKです。2を両方に分配して、そのあとは余りが3のときと同じでいつも4の剰余の条件は満たします。
2が3個の場合、例えば24の場合、4と6に分割するとダメですね。どうやってもダメなことが分かるでしょう。
2が4個以上の場合、4を両方に分配すればやっぱりあとは余り3のときと同じです。
5.5秒になりました。