解法のひとつです。
幾何数列に着目するってもの考えたんだけどなあ。
いまいち無理でしたｗ
幾何数列「a, ca, c^2 a」における比率を「c」とします。 gcd(p, q) == 1 の場合、c は p/q と書くことができます。 したがって、n^2 == c^3*a^2 + a がわかります。 'a' は整数 k に対して k*q^2 の形式でなければならないため、 n^2 == (k * p^3 + q) * k * q であることがわかります。 したがって、p>q および gcd(p,q) == 1 である 3 つの整数 p, q, k を探す必要があります。 制限は q < LIMIT^(1/4) であり、p は (p^ 3+q)*q < LIMIT。
まず、この最初の部分。
幾何数列「a, ca, c^2 a」における比率を「c」とします。 gcd(p, q) == 1 の場合、c は p/q と書くことができます。 したがって、n^2 == c^3*a^2 + a がわかります。
幾何数列のどれが d, q, r になるかについては、
n^2 = d * q + r なので、r は必ず r < d かつ r < q となる。
また、d, q はどちらが最大の値を取るにしても、掛け算になるのでどちらでもかまわない。
つまり、幾何数列では一番小さい a の部分が r になる。
n^2 = d * q + r
は、
n^2 = c^2a * ca + a n^2 + c^3 * a^2 + a
と書き換えることができる。ここまでは難しくないね。
次。
'a' は整数 k に対して k*q^2 の形式でなければならないため、 n^2 == (k * p^3 + q) * k * q であることがわかります。
ここの a を整数 k に対して置き換えるってのが、なかなか思いつけないんだよね。ここが難しい。
幾何数列「a, ca, c^2 a」における比率を「c」とします。 gcd(p, q) == 1 の場合、c は p/q と書くことができます。
これから幾何数列
a, ca, c^2a
は
a, p/q * a, p^2/q^2 * a
と書ける。
各項の公比 p/q の分母部分を消したいのと、
幾何数列だからすべての項に同じものを乗算しても公比が崩れなければ問題ないので、
a = k * q^2 って事にする。
(公比が分数だと計算がすごく面倒になるし、誤差の問題がつきまとうので、分母は消してしまいたい。)
つまり幾何数列
a, p/q * a, p^2/q^2 * a
は整数 k を用いて a = k * q ^ 2 と書けるため、
k * q ^ 2, k * p * q, k * p^2
と書き替えることができる。
さらに
n^2 = c^3 * a^2 + a
は c = p/q, a = k * q^2 から
n^2 = (k * p^3 + q) * k * q
が導かれる。
ってことでいいんかな？
最後の部分
したがって、p>q および gcd(p,q) == 1 である 3 つの整数 p, q, k を探す必要があります。 制限は q < LIMIT^(1/4) であり、p は (p^ 3+q)*q < LIMIT。
1行目はいいとして、q と p をどこまで走査すればいいかの部分は、
計算の途中で q^4 が出てきます。ただし約分するので実際に q^4 は計算しないですが、
このため LIMIT^(1/4) 未満とすれば良いのかな。たぶん。
p のほうは前述の
n^2 = (k * p^3 + q) * k * q
この式から k を省くと p は (p^ 3+q)*q < LIMIT までにすれば良さそう。
なんとなくだけど。こんな理解で良いんかな？
あとはプログラムにするだけなんですけども、これは割愛します。
完成したプログラムは爆速で解答してくれるはずです。
