自动搬运

查看原文

来自洛谷，原作者为

	灰鹤在此 饭可以一日不吃，觉可以一日不睡，車不可以一日不开

搬运于2025-08-24 22:33:01，当前版本为作者最后更新于2021-09-24 16:55:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解是基于 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$ 这样一条恒不等式。但是我们要求的是正整数解，那么这个问题就变成了佩尔方程的变形。

• 因为当 $k\in Z_{\ge1}$ 的时候，即 $d$ 为平方数的时候，这个不等式非常好解。因为当 $y\ge 1$ 的时候，$x+k\cdot y\ge1$，所以 $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$ 为平方数的时候，我们所求的答案为

• 当 $k$ 是无理数的时候，我们可以用连分数来解决这个问题。

先来介绍一下 $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;
}