由费尔马提出，但后来欧拉误记为佩尔提出，并写入他的著作中。后人多称佩尔方程。沿续至今

简介

对于 当n为完全平方数时无解；

C++程序求解佩尔方程：

简介

设d是正整数，且非平方数。

下面的不定方程称为佩尔（Pell）方程：

x^2-dy^2=1……①

①一定有无穷多组正整数解

这是初等数论中最经典的内容之一。

假设(x_0,y_0)是①中使x+y^0.5最小的解（称为①的基本解）， 那么①的所有的正整数解可写为

x_n=1/2[(x_1+y_1d^0.5)^n+(x_1-y_1d^0.5)^n]

y_n=1/(2d^0.5)[(x_1+y_1d^0.5)^n-(x_1-y_1d^0.5)^n]

∴x_n+y_n*(d)^0.5=(x_0+y_0*(d)^0.5)^(n+1)

且不难导出x_n,y_n满足的线性递推关系

x_n=2x_1x_(n-1)-x_(n-2)

y_n=2x_1y_(n-1)-y_(n-2)

佩尔方程与连分数，二次型，代数数域等等都有密切联系。

在一般的函数域上，我们也有类似的佩尔方程， 它和向量丛的稳定性有着微妙的关系。

以上的公式就是Pell方程的一般形态.

对于 当n为完全平方数时无解；

1. 首先构造一个系数矩阵,显然为了构造这个矩阵，我们需要先得到

下面方程的一个最小特解(x,y>0)

利用Euler的算法

1: p[−1] ⇐ 1; p[−2] ⇐ 0

2: q[−1] ⇐ 0; q[−2] ⇐ 1

3: a[0] ⇐sqrt(n)

4: g[−1] ⇐ 0; h[−1] ⇐ 1

5: for i = 0 → ∞ do

{

6: g[i] ⇐ −g[i−1] + a[i]h[i−1]

7: h[i] ⇐ （n−g[i]*g[i]） / h[i-1]

8: a[i+1] ⇐ floor( (g[i]+a[0]) / h[i]

9: p[i] ⇐ a[i]p[i−1] + p[i−2]

10: q[i] ⇐ a[i]q[i−1] + q[i−2]

if( p[i]*p[i]-n*q[i]*q[i]=1 ) return (p[i],q[i]);

}假设我们得到了以上方程的最小特解: x0 y0 (x0,y0>0,并是最小的满足条件的解)

C++程序求解佩尔方程：

#include <iostream>

#include <cmath>

using namespace std;

struct PellAns

{

int p,q;

};

struct Node

{

int g,h;

};

PellAns Solve( int n)

{

PellAns s[4];

Node w[4];

int a[4];

s[0].p=0; s[0].q=1;

s[1].p=1; s[1].q=0;

a[0]=(int)floor(sqrt( (double)n ));

a[2]=a[0];

w[1].g=0;w[1].h=1;

while( 1 )

{

w[2].g = -w[1].g+a[2]*w[1].h;

w[2].h = (n-w[2].g*w[2].g)/w[1].h;

a[3] = (int)floor( (double)(w[2].g+a[0])/w[2].h );

s[2].p = a[2]*s[1].p+s[0].p;

s[2].q = a[2]*s[1].q+s[0].q;

if( (s[2].p*s[2].p-n*s[2].q*s[2].q) == 1 &&s[2].p>0&&s[2].q>0 )

return s[2];

w[0]=w[1];w[1]=w[2];

a[2]=a[3];

s[0]=s[1];s[1]=s[2];

}

}

int main()

{

int n;

PellAns ans;

while( scanf("%d",&n) )

{

ans = Solve(n);

printf("%d %d\",ans.p,ans.q);

}

return 0;

}