奇妙的平方数拆分组合(内含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的解