P7779 『JROI-2 / Stoi2039』等你下课题解

· · 题解

本题解是基于 VinstaG173 的题解所做的一些补充和改进。

题目要求的是所有 x^2-d\cdot y^2(x,y\in N) 的值 v 的和。且 v\in[1,\sqrt{d}]。

我们设 k=\sqrt{d}，于是我们可以得到 k\ge (x+k\cdot y)(x-k\cdot y)\ge1 这样一条恒不等式。但是我们要求的是正整数解，那么这个问题就变成了佩尔方程的变形。

于是我们得到 x\ge k\cdot y+1，代回得 x+k\cdot y\ge 2k\cdot y+1，而因为 k\ge (x+k\cdot y)(x-k\cdot y) 且 x-k\cdot y\ge1，这个不等式无解，所以 y=0。

当 y=0 的时候，只要 v 是在限制范围内的平方数，那么一定有对应的 x 可以使原方程成立，所以当 d 为平方数的时候，我们所求的答案为

\sum_{i=1}^{\sqrt{k}}i\times i

先来介绍一下 Pell 方程：

形如 x^2-d\cdot y^2=1 的方程。

假设 (x_0,y_0) 是它的最小正整数解，那么这个方程的所有正整数解可写为：

x_n=\frac{(x_1+\sqrt d\cdot y_1)^n+(x_1-\sqrt d\cdot y_1)^n}{2} y_n=\frac{(x_1+\sqrt d\cdot y_1)^n+(x_1-\sqrt d\cdot y_1)^n}{(2\sqrt d)}

所以 x_n+\sqrt d\cdot y_n=(x_0+\sqrt d\cdot y_0)^{n+1}。

且 x_n 和 y_n 之间存在线性关系。

x_n=2\cdot x_1\cdot x_{n-1}-x_{n-2} y_n=2\cdot y_1\cdot y_{n-1}-y_{n-2}

况且，我们还可以用连分数来求解 Pell 方程。

我们现在要处理的是 Pell 方程的变形。

因为 (x+k\cdot y)(x-k\cdot y)=v，如果当 \frac{x}{y} 等于 k 的一个渐进分数，那么 v 就是我们再求 k 的渐进分数中的过渡数 c。

接下来就是如何求二次无理数的连分数和过渡数：

请阅读连分数这篇博客里面不失精度的求无限连分数的方法。

我们要求的是所有过渡数的和，而且每一种数我们只能计算一次。因为我们求得的过渡数都是正的，但是我们不能保证 x 和 y 都是正的，因为 (-1)^n\cdot c_n=p_{n-1}^2-d\cdot q_{n-1}^2，所以我们要先把所有偶数次求的过渡数先加上（因为肯定是正数），然后再根据我们求得的连分数的循环节的奇偶性来判断我们后面是否需要把奇数次求得的过渡数再加上。

因为如果循环节是奇数，那么它下一次循环的时候，奇数次位置上的数会跑到偶数次位置上来，所以如果循环节是奇数，那么所有奇数次上的数都要再加一遍。

代码

#include<bits/stdc++.h>
using namespace std;
const int MaxN=2e6+5;
const int MaxD=1e4+5;
const int MaxK=1414;
int T,d,vis[MaxN],state[MaxK+5],a[MaxD],c[MaxD],k[MaxD],cnt,ans,sk,ssk;
int main(){
    for(register int i=1;i<=MaxK;i++){
        vis[i*i]=1;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&d);
        sk=sqrt(d);
        ssk=sqrt(sk);
        cnt=ans=0;
        for(register int i=1;i<=ssk;i++){
            ans+=i*i;
            state[i*i]=1; 
        }
        if(!vis[d]){
            a[0]=sk;
            c[0]=1;
            k[0]=0;
            while(a[cnt]!=sk*2){
                k[cnt+1]=a[cnt]*c[cnt]-k[cnt];
                c[cnt+1]=(d-k[cnt+1]*k[cnt+1])/c[cnt];
                a[cnt+1]=(sk+k[cnt+1])/c[cnt+1];
                cnt++;
                if(!(cnt&1)){
                    if(c[cnt]<=sk){
                        if(!state[c[cnt]]){
                            ans+=c[cnt];
                            state[c[cnt]]=1;
                        }
                    }
                }
            }
            if(cnt&1){
                for(register int i=1;i<=cnt;i+=2){
                    if(c[i]<=sk){
                        if(!state[c[i]]){
                            ans+=c[i];
                            state[c[i]]=1;
                        }   
                    }
                }
            }
            for(register int i=1;i<=sk;i++){
                state[i]=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}