自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:07:53，当前版本为作者最后更新于2021-09-14 14:36:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

简单类欧题，给定 $n,r$ 求：

$$\sum_{d=1}^{n}(-1)^{\left\lfloor d\sqrt{r} \right\rfloor} $$

如果 $r$ 能开出来就太好了，可惜不一定可以，所以我们需要推式子。

简单处理

当 $\sqrt r\equiv 0\pmod 2$ 那么答案就是 $n$，因为一共是 $n$ 个 $1$ 相加，如果 $\sqrt r\equiv 1\pmod 2$，那么答案就要考虑 $n$ 的奇偶性，如果 $n$ 是偶数就输出 $0$ 否则输出 $-1$。

那如果 $\sqrt r$ 开出来是一个无理数怎么办呢？

考虑 $-1$ 次幂的最基本推导：$(-1)^{2n}=1$，那么就可以写出式子 $(-1)^x=1-2(x\bmod 2)$。而考虑取余运算的基本定义，我们可以写出：

$$(-1)^x=1-2\left(x-2\left\lfloor\dfrac{x}{2}\right\rfloor\right)=1-2x+4\left\lfloor\dfrac{x}{2}\right\rfloor $$

将这个式子代入到原式之中，就得到：

$$\sum_{d=1}^{n}1-2\left\lfloor d\sqrt{r} \right\rfloor+4\left\lfloor\dfrac{\left\lfloor d\sqrt{r} \right\rfloor}{2}\right\rfloor $$

将其中无关紧要的部分写开来，就是：

$$n+2\sum_{d=1}^{n}\left\lfloor d\sqrt{r} \right\rfloor+4\sum_{d=1}^{n}\left\lfloor\dfrac{d\sqrt{r}}{2}\right\rfloor $$

接下来就是类欧的重头戏了。

类欧化简

设 $f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor\dfrac{a\sqrt r+b}{c}\cdot i\right\rfloor$，那么题目所求就是：

$$n-2f(1,0,1,n)+4f(1,0,2,n)$$

不妨令 $x=\sqrt r$，$t=\dfrac{ax+b}{c}$，更方便地表示这个式子：

$$f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor ti\right\rfloor $$

然后就可以分类讨论。

分类讨论

我们对于 $t$ 的大小进行简单的考虑。

若 $t\ge 1$：

记 $\lfloor t\rfloor$ 为 $\alpha$ 那么就可以写出：

$$f(a,b,c,n)=\sum\limits_{i=1}^{n}\left\lfloor ti\right\rfloor=\sum\limits_{i=1}^{n}\left\lfloor ti-\alpha i+\alpha i\right\rfloor $$

将 $t$ 值代入进去就得到：

$$\dfrac{(n+1)n}{2}\alpha+\sum\limits_{i=1}^{n}\left\lfloor\left(\dfrac{ax+b}{c}-\alpha\right)i\right\rfloor $$

不难发现，式子中 $\alpha$ 移到分母上之后就得到了该式子的递归化简式：

$$f(a,b-c\alpha,c,n)+\dfrac{(n+1)n}{2}\alpha$$

若 $t<1$：

那么，由于 $t$ 的正负性，不难发现 $\alpha$ 就应该为 $0$，那么我们可以利用贡献思想进行一个简单的推论：

$$f(a,b,c,n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left[j<ki\right] $$

然后在谓词函数里做一个简单的代数变换：

$$f(a,b,c,n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left[\dfrac{j}{t}<i\right] $$

然后调换求和顺序：

$$\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\sum\limits_{i=1}^{n}\left[i>\dfrac{j}{t}\right] $$

这样意义是将限制条件转换到内部的和式之中，从而达到化简的目的：

$$\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{t}\right\rfloor\right) $$

这时候如果将 $t$ 值代入，很有意思的情况就会出现：

$$\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{\dfrac{ax+b}{c}}\right\rfloor\right) $$

化为正常形式：

$$\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left(n-\left\lfloor\dfrac{j}{ax+b}\cdot c\right\rfloor\right) $$

将 $j$ 和 $c$ 的位置互换，然后把 $n$ 提出来：

$$n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{c}{ax+b}\cdot j\right\rfloor $$

右边是什么？是非常接近最初形式的一个式子，考虑将他化成最初形式，乘上分母的共轭：

$$n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{c(ax-b)}{(ax+b)(ax-b)}\cdot j\right\rfloor $$$$n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{cax-cb}{a^2x^2-b^2}\cdot j\right\rfloor $$

这已经很接近结果了，但是我们考虑到 $x^2$ 是等同于 $r$ 的，于是写作：

$$n\cdot \left\lfloor{nt}\right\rfloor-\sum\limits_{i=1}^{\left\lfloor{nt}\right\rfloor}\left\lfloor\dfrac{cax-cb}{a^2r-b^2}\cdot i\right\rfloor $$

写成一般形式：

$$f(a,b,c,n)=n\cdot \left\lfloor{nt}\right\rfloor-f(ca,-cb,a^2r-b^2,\left\lfloor{nt}\right\rfloor) $$

所以我们已经得到答案了，所以我们能够很容易写出代码。

代码实现

代码实现的一些细节在于，我们应当要把下取整部分提前算出，否则在式子的运算中会到最后才进行下取整。

#include<bits/stdc++.h>
#define int long long
using namespace std;
double x;
int T,n,r;
int f(int a,int b,int c,int n){
	if(n==0)return 0;
	int gcd=__gcd(a,__gcd(b,c));
	a/=gcd,b/=gcd,c/=gcd;
	int t=(a*x+b)/c;
	if(t!=0)return n*(n+1)/2*t+f(a,b-c*t,c,n);
	else{
		int kn=(a*x+b)*n/c;
		return n*kn-f(a*c,-b*c,a*a*r-b*b,kn);
	}
}signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&r);
		x=sqrt(r);
		int s=(int)x;
		if(s*s==r){
			if(s%2==0)printf("%lld\n",n);
			else if(n%2==0)puts("0");
			else puts("-1");
		}else printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
	}return 0;
}