佩尔方程_牛客博客

佩尔方程

$x^2-D\cdot y^2=1$
当 $D$ 是平方数时,方程无解,当 $D$ 为非平方数时无穷解.
若得到该方程的最小解 $x_1,y_1$ ，可有递推方程得到.

$x_{n+1}=x_1 \cdot x_n+D \cdot y_1 \cdot y_n$
$y_{n+1}=x_1 \cdot y_n+y_1 \cdot x_n$

求最小解用连分数

ll a[200000];
bool pell(ll D,ll &x,ll &y){
    ll m=(ll)sqrt(0.5+D);double sq=sqrt(D);
    if(m*m==D)return false;
    int i=0;a[i++]=m;ll b=m,c=1;
    double tmp;
    do{
        c=(D-b*b)/c;  tmp=(sq+b)/c;
        a[i++]=(ll)(floor(tmp));b=a[i-1]*c-b;
    }while(a[i-1]!=2LL*a[0]);
    ll p=1,q=0;
    for(int j=i-2;j>=0;j--){
        ll t=p;p=q+p*a[j];q=t;
    }
    if((i-1)%2==0)x=p,y=q;
    else x=2LL*p*p+1,y=2LL*p*q;
    return true;
}