奇妙的平方数拆分组合(内含Pell方程链接)

medie2005

呵呵，在17#中还有一点没说清楚： 如何直接求解(1)？ 我们在两边同除以$y^{2}$，得到一个关于$x/y$的方程。用韦达定理求解，就可以得到$x/y$的值，将这个值用连分数展开，就得到了x,y。

mathe

你这个还是不行,右边还有常数$c^2$,不是关于x,y的其次式,没法这样的.同样17#最后面部分也不可用.还是得用我的方法

medie2005

常数$c^2$是可以忽略的，这样才用连分数来求x,y。

mathe

方程$y^2-10^k x^2=c^2$ 在k为偶数时，就是一个特殊的勾股数问题，很容易解决。 而在k为奇数的时候，我们可以设$t=10^{(k-2)/2}*x$ 于是方程变成 $y^2-10t^2=c^2$ 所以是一个Pell方程。 这个Pell方程，如果5|c,很显然我们可以马上得到5|y和5|t,分别除掉5以后方程还是这个形式，所以我们可以假设c不是5的倍数，然后 我们知道所有的解的形式只能是下面4种之一 $(y-c)=10a^2,y+c=b^2$ $(y-c)=5a^2,y+c=2b^2$ $(y-c)=2a^2,y+c=5b^2$ $(y-c)=a^2,y+c=10b^2$ 分别对他们进行变换，可得变成 $b^2-10a^2=+-2c$ 或 $2b^2-5a^2=+-2c$ 形式的方程，而后面一种方程a是2的倍数，将a替换成2a以后方程就变成 $b^2-10a^2=+-c$ 所以我们问题归结为就Pell方程 $b^2-10a^2=+-c$或 $b^2-10a^2=+-2c$ 的解。 http://hometown.aol.com/jpr2718/ 中给出了若干种求解这种类型Pell方程的解的方法， 比如其中穷举法使用的时间复杂度也就在$O(sqrt(c))$ 所以通过这个方法我们可以穷举c到一定的范围（比如$2^16$). 当然其中还提到更加复杂的LMM算法，但是我没有看到算法时间复杂度的介绍。 这篇文章我已经下载了，所以直接作为附件放在这里： pell.pdf (168.46 KB, 下载次数: 45)

2008-10-31 17:36 上传

点击文件名下载附件

medie2005

$t=10^{(k-2)/2}*x$ 应该是: $t=10^{(k-1)/2}*x$ 另外,这个变换在k较大的时候约束太强了. k=5,则$t=100*x$ 这就要求解得的a,b满足: 100|a*b. 这是不太容易满足的.

medie2005

另外,我刚看了一下mathe附件的那篇论文,发现好像用穷举的复杂度并不是只取决于c,还取决于方程最小解.

mathe

原帖由 medie2005 于 2008-10-31 19:46 发表 另外,我刚看了一下mathe附件的那篇论文,发现好像用穷举的复杂度并不是只取决于c,还取决于方程最小解.

D=10时方程最小解已知19^2-10*6^2=1

medie2005

呵呵。漏看了。还以为是x^2-Dy^2=c的最小解呢。

medie2005

现在，考虑立方情形。 即求解丢番图方程： $x^{3}*10^{k}+y^{3}=z^3$ 其中，$10^{k-1}<=y^{3}<10^k$ 当3|k时，无解。 对其他情形的k，是否有解？能否找出一个解？

无心人

可以先暴力求下k=1的解