ProjectEuler 404 - Crisscross Ellipses

专注数论分析三十年。

暴力跑了 2min ……

如果你想享受做题的乐趣就不要看啦。。

好了如果你还在看的话那就不能享受做题的乐趣了。。

事实上就是要快速枚举 \(a^2 + 4 b^2 = p^2\) （ \(a, b, c\) 均为奇数，且 \(gcd(a,b,c) = 1\) ）。

换元令 \(a = c + 2i, b = c - j\) ，代入后整理得 \(p = \frac{i^2 +j^2}{2j - i}\) 。

再次换元令 \(t = 2j - i\) ，代入后整理得 \(p = \frac{5j^2}{t} + t - 4j\) 。

枚举 \(j\) 即可。

相关点：如果 \(a^2+b^2=c^2\) ，则将 \(a + b i\) 分别乘上 \(1 + 2i\) 和 \(1 - 2i\) 就可以得到 \(a^2 + b^2 = 5c^2\) 的解。

而且这是个丢番图方程，用一个奇怪的方法叫做割线法可以求？

关于 \(a x^2 + b y^2 = c z^2\) 有一种方法可以快速枚举出来……名字叫做 Lagrange's trick ？

首先两边都乘以 \(a\) ，把原方程化为 \(x^2 + by^2 = cz^2\) 这种样子。

首先我们需要找到任意一组解 \((x_0, y_0, z_0)\) 。考虑

\[ \begin{array}{rl} (cz_0 z)^2 & = c^2 z^2_0 z^2 \\ & = (x^2_0 + b y^2_0) (x^2 + b y^2) \\ & = (x_0 x + b y_0 y)^2 + b (x_0 y - y_0 x)^2 \\ \end{array} \]

然后再考虑 \(x^2 + b y^2 = z^2\) 该怎么解。显然 \(b y^2 = (z - x)(z + x)\) 。分解质因数 \(b = b_1 b_2\) ，令 \(y^2 = \frac{z-x}{b_1} \frac{z+x}{b_2}\) ，然后就可以令 \(y = tpq, \frac{z-x}{b_1} = tp^2, \frac{z+x}{b_2} = tq^2\) ，其中 \(p, q\) 互质。枚举 \(p, q\) 保证得到的数是整数即可。