【概述】

連分?jǐn)?shù)是一種特殊的繁分?jǐn)?shù)，其形式為：??，通常記為：，其中? 和 ?稱為連分?jǐn)?shù)多項(xiàng)式，對于任意的 a 均為一次式，它們的比值稱為第 n 個漸進(jìn)值漸進(jìn)分?jǐn)?shù)。

佩爾（Pell）方程是一種不定二次方程，其與連分?jǐn)?shù)，二次型，代數(shù)論等有著重要的聯(lián)系。

其形式為：，其中 d?不為非平方數(shù)

【佩爾方程迭代公式】

定義：設(shè) p、q 為整數(shù)，且滿足?，則稱??給出該方程的解

推論：

設(shè)??給出方程??的解

則：?給出方程??的解，其中?

取?，則有佩爾方程??

若佩爾方程的最小特解為?，故有迭代公式：

將迭代公式寫為矩陣的形式，有：，可以通過矩陣快速冪找出第 k 大的解

【連分?jǐn)?shù)求解佩爾方程】

對于連分?jǐn)?shù) ?的漸進(jìn)值來講，有著遞歸關(guān)系式：

通過數(shù)學(xué)歸納法，可得到關(guān)系式：

定義：對于正整數(shù) p、q，若有?，則比值??必為 a 的一個漸近值

由此可得：佩爾方程的全部根的集合為?

由佩爾方程的迭代公式可得出佩爾方程的最小解

即：

【模版】

1.暴力尋找最小解

int x[N],y[N]; void pell(int &a,int &b,int d){//暴力尋找pell方程最小解b=1;while(true){a=(LL)sqrt(d*b*b+1);if(a*a-d*b*b==1)break;b++;} } int main(){int d;while(scanf("%d",&d)!=EOF){int m=(int)sqrt((double)d);if(m*m==d){//d不能為完全平方數(shù)cout<<"No Solution"<<endl;continue;}int a=0,b=0;pell(a,b,d);//暴力找到最小解cout<<a<<" "<<b<<endl;}return 0; }

2.迭代公式求前 n 個解

使用迭代公式求解 pell 方程的前 n 個解時，應(yīng)先用暴力尋找到最小解，然后再套用迭代公式求出前 n 個解，由于 pell 方程相鄰兩解之間的差值較大，n 一般很小

int x[N],y[N]; void pell(int &a,int &b,int d){//暴力尋找pell方程最小解b=1;while(true){a=(LL)sqrt(d*b*b+1);if(a*a-d*b*b==1)break;b++;} } int main(){int d;while(scanf("%d",&d)!=EOF){int m=(int)sqrt((double)d);if(m*m==d){//d不能為完全平方數(shù)cout<<"No Solution"<<endl;continue;}int a=0,b=0;pell(a,b,d);//暴力找到最小解x[1]=a,y[1]=b;//第一組解for(int i=2;i<=10;i++){//遞推公式x[i]=x[i-1]*x[1]+2*y[i-1]*y[1];y[i]=x[i-1]*y[1]+y[i-1]*x[1];}for(int i=1;i<=10;i++)cout<<x[i]<<" "<<y[i]<<endl;}return 0; }

3.連分?jǐn)?shù)法

當(dāng)要求 pell 方程的最小解時，暴力可能會 TLE，此時可以使用連分?jǐn)?shù)法，其關(guān)鍵是計算連分?jǐn)?shù)的展開

int a[20000]; bool pell(int &x,int &y,int d){int m=(int)sqrt((double)d);if(m*m==d)//d不能為完全平方數(shù)return false;//將d以連分?jǐn)?shù)形式存儲int num=0;//連分?jǐn)?shù)數(shù)位double sq=sqrt(d);//d的高精度根，相當(dāng)于r0a[num++]=m;//存儲整數(shù)部分int b=m;//當(dāng)前整數(shù)部分int c=1;//連分?jǐn)?shù)最終展開時的分母double temp;//連分?jǐn)?shù)展開時的每一項(xiàng)do{c=(d-b*b)/c;temp=(sq+b)/c;a[num++]=(int)(floor(temp));b=a[num-1]*c-b;}while(a[num-1]!=2*a[0]);//當(dāng)有一位等于整數(shù)兩倍時結(jié)束//將連分?jǐn)?shù)形式化為分子分母形式，即求p、q兩個值int p=1,q=0;for(int i=num-2;i>=0;i--){int temp=p;p=q+p*a[i];q=temp;}if((num-1)%2){//連分?jǐn)?shù)長度為奇數(shù)時x=2*p*p+1;y=2*p*q;}else{//連分?jǐn)?shù)長度為偶數(shù)時x=p;y=q;}return true; } int main(){int d;while(scanf("%d",&d)!=EOF){int x,y;if(pell(x,y,d))cout<<x<<" "<<y<<endl;elsecout<<"No Solution"<<endl;}return 0; }

【例題】

• Street Numbers（POJ-1320）(佩爾方程)：點(diǎn)擊這里
• Square Number（HDU-2281）(佩爾方程)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的数论 —— 佩尔方程与连分数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。