递推算法,没看出递推

realnumber

极值问题
时间限制: 1 Sec  内存限制: 128 MB
题目描述
已知m,n为整数，且满足下列两个条件：
①m,n∈{1,2, …,k},即1≤m,n≤k;
②$(n^2-m*n-m^2)^2=1$.
编程输入正整数k($1≤k≤10^9$)，求一组满足上述两个条件的m,n,并且使$m^2+n^2$的值最大。（p163）
输入：
正整数k。
输出：
满足上述两个条件的m,n。
样例输入
1995
样例输出
m=987
n=1597
提示：递推算法

hejoseph

其实就是一个 Pell 方程的求解问题：$n^2-mn-m^2=\pm 1$，即 $(2n-m)^2-5m^2=\pm 4$。$m$ 是偶数，方程变为 $(n-m_1)^2-5m_1^2=\pm 1$，其中 $m=2m_1$，这是一般的 Pell 方程。若 $m$ 是奇数，则 $2n-m$ 和 $m$ 必定互素。

设 $D$ 是非完全平方数的正整数，则
Pell 方程 $x^2-Dy^2=1$ 的通解是 $x+\sqrt Dy=\left(x+\sqrt Dy_0\right)^k$，其中 $(x_0,y_0)$ 是满足 $x_0>0$，$y_0>0$ 的最小解，$k$ 是任意正整数。
Pell 方程 $x^2-Dy^2=-1$ 的通解是 $x+\sqrt Dy=\left(x+\sqrt Dy_0\right)^{2k-1}$，其中 $(x_0,y_0)$ 是满足 $x_0>0$，$y_0>0$ 的最小解，$k$ 是任意正整数。

Pell 方程 $Ax^2-By^2=4$（$A$、$B$ 是正整数，且不同时为完全平方数）满足$x>0$，$y>0$，$x$、$y$ 互素的通解是
\[
\frac{\sqrt Ax+\sqrt By}{2}=\left(\frac{\sqrt Ax_0+\sqrt By_0}{2}\right)^{6k-5}
\]
其中 $(x_0,y_0)$ 是满足 $x_0>0$，$y_0>0$ 的最小解，$k$ 是任意正整数。由此就能写出递归公式了。

hejoseph

题目中
$(n-m_1)^2-5m_1^2=1$ 的通解是
\[
n-m_1+\sqrt 5m_1=\left(9+4\sqrt 5\right)^k
\]

$(n-m_1)^2-5m_1^2=-1$ 的通解是
\[
n-m_1+\sqrt 5m_1=\left(2+\sqrt 5\right)^{2k-1}
\]

$(2n-m)^2-5m^2=4$ 的通解是
\[
\frac{2n-m+\sqrt 5m}{2}=\left(\frac{3+\sqrt 5}{2}\right)^{6k-5}
\]

$(2n-m)^2-5m^2=-4$ 的通解是
\[
\frac{2n-m+\sqrt 5m}{2}=\left(\frac{1+\sqrt 5}{2}\right)^{6k-5}
\]

其妙

那不是斐波那契数列的性质么？可以考虑构造斐波那契数列

hejoseph

是线性递归关系，但不是 Fibonacci 数列那种

realnumber

由3楼
$(n-m)^2-5m^2=1$ 的通解是
\[n-m+\sqrt 5m=\left(9+4\sqrt 5\right)^k\]
k，k-1对应的解为$(n_1,m_1),(n_2,m_2),$则由上面通解得
$n_1=13n_2+16m_2,m_1=4n_2+5m_2$
检验了(1,0)到(13,4)
有没其他途径得到这个关系或其它关系等

isee

回复 6# realnumber


    应该没有了，数论中的基础

realnumber

baike.baidu.com/item/佩尔方程/11029962?fr=aladdin
$x_n=2x_1x_{n-1}-x_{n-2}$
$y_n=2x_1y_{n-1}-y_{n-2}$
其中$(x_1,y_1)$是$x^2-Dy^2=1$的最小正整数解.
按上面思路编程就很“数学”了，耗时近于O($log_{x_1}k$).
另：可以按
for  n=k downto 1 do { m,n关系写为一元二次方程求根公式，m为整数  },直接搜索，找到就是$m^2+n^2$最大,猜是也能通过或大部分通过,耗时最差O($x_{n+1}-x_{n}$).

realnumber

4楼  说得对
可以用数学归纳法证明，斐波那契数列连续两项符合1楼递推关系
假设m,n(m<n)可以,则n,m+n也符合

反过来 可以用无穷递降法证明，符合递推关系，就是斐波那契数列数列中连续两项.
若m,n(m<n)可以,则n-m,m也一定符合，直至为0,1