（未完待续）一道神奇的 类欧几里得算法 题目。

题目链接：Luogu P5172/BZOJ 3817/UOJ 42/清华集训2014 D3T1。

题目

题目描述

$T$ 组数据，给定正整数 $n,r$，求：

$$\sum _ {d=1}^n(-1)^{\lfloor d\sqrt{r}\rfloor}$$

数据范围

时空限制

题解

思路

思路其实就是推式子得出来的。

化简式子

$$
\begin{aligned}
\sum _ {d=1}^n(-1)^{\lfloor d\sqrt{r}\rfloor}&=\sum _ {d=1}^n(1-2\times(\lfloor d\sqrt{r}\rfloor\bmod 2))\\
&=\sum _ {d=1}^n1-2\sum _ {d=1}^n(\lfloor d\sqrt{r}\rfloor\bmod 2)\\
&=n-2\sum _ {d=1}^n(\lfloor d\sqrt{r}\rfloor\bmod 2)\\
&=n-2\sum _ {d=1}^n(\lfloor d\sqrt{r}\rfloor-\times\lfloor\frac{\lfloor d\sqrt{r}\rfloor}{2}\rfloor)\\
&=n-2(\sum _ {d=1}^n\lfloor d\sqrt{r}\rfloor-\sum _ {d=1}^n2\lfloor\frac{\lfloor d\sqrt{r}\rfloor}{2}\rfloor)\\
&=n-2(\sum _ {d=1}^n\lfloor d\sqrt{r}\rfloor-2\sum _ {d=1}^n\lfloor\frac{\lfloor d\sqrt{r}\rfloor}{2}\rfloor)\\
&=n-2\sum _ {d=1}^n\lfloor d\sqrt{r}\rfloor+4\sum _ {d=1}^n\lfloor\frac{\lfloor d\sqrt{r}\rfloor}{2}\rfloor\\
&=n-2\sum _ {d=1}^n\lfloor d\sqrt{r}\rfloor+4\sum _ {d=1}^n\lfloor\frac{d\sqrt{r}}{2}\rfloor\\
\end{aligned}
$$

类欧几里得算法的应用

于是我们考虑用 类欧几里得算法 来快速求出 $\sum _ {d=1}^n\lfloor d\sqrt{r}\rfloor$ 和 $\sum _ {d=1}^n\lfloor\frac{\lfloor d\sqrt{r}\rfloor}{2}\rfloor$。

考虑设 $f(n,a,b,c)=\sum _ {i=1}^n\lfloor i\times\frac{a\sqrt{r}+b}{c}\rfloor$，那么我们有：

$$\texttt{ans}=n-2f(n,1,0,1)+4f(n,1,0,2)$$

下面考虑怎样快速求函数 $f$ 的值。

首先不难发现一个边界条件 $f(0,\forall a,\forall b,\forall c)=0$。

再次观察 $f$ 的表达式 $f(n,a,b,c)=\sum _ {i=1}^n\lfloor i\times\frac{a\sqrt{r}+b}{c}\rfloor$，发现：

1. 设 $k=\frac{a\sqrt{r}+b}{c}$，则 $f(n,a,b,c)=\sum _ {i=1}^n\lfloor ik\rfloor$。
2. 将 $i$ 视作平面直角坐标系中的 $x$ 坐标，不难发现 $f(n,a,b,c)$ 的含义是：斜率为 $k$ 的过原点直线与 $x$ 正半轴在坐标范围为 $[1,n]$ 时围成的三角形内（上）的整点个数（$x$ 轴上的不算）。

进一步的推论

根据上述规律，我们不难看出，如果 $k>1$，我们有：

$$
\begin{aligned}
f(n,a,b,c)&=\sum _ {i=1}^n\lfloor i\times\frac{a\sqrt{r}+b}{c}\rfloor\\
&=\sum _ {i=1}^n\lfloor ik\rfloor\\
&=\sum _ {i=1}^n\lfloor i(k-\lfloor k\rfloor+\lfloor k\rfloor)\rfloor\\
&=\sum _ {i=1}^n\lfloor i(k-\lfloor k\rfloor)\rfloor+\sum _ {i=1}^ni\lfloor k\rfloor\\
\end{aligned}
$$

考虑之前发现的性质，我们有

$$\sum _ {i=1}^ni\lfloor k\rfloor=\frac{n(n+1)\lfloor k\rfloor}{2}$$

所以我们继续推上面的式子。

$$
\begin{aligned}
f(n,a,b,c)&=\sum _ {i=1}^n\lfloor i(k-\lfloor k\rfloor)\rfloor+\sum _ {i=1}^ni\lfloor k\rfloor\\
&=\sum _ {i=1}^n\lfloor i(k-\lfloor k\rfloor)\rfloor+\frac{n(n+1)\lfloor k\rfloor}{2}\\
&=\sum _ {i=1}^n\lfloor i(\frac{a\sqrt{r}+b}{c}-\lfloor k\rfloor)\rfloor+\frac{n(n+1)\lfloor k\rfloor}{2}\\
&=\sum _ {i=1}^n\lfloor i\frac{a\sqrt{r}+b-c\lfloor k\rfloor}{c}\rfloor+\frac{n(n+1)\lfloor k\rfloor}{2}\\
&=f(n,a,b-c\lfloor k\rfloor,c)+\frac{n(n+1)\lfloor k\rfloor}{2}\\
\end{aligned}
$$

画图，寻求最终答案

上述式子的推理中始终没有缩小 $n$ 的范围，无法减少时间复杂度，于是我们考虑使用一些技巧缩减 $n$ 的范围。

对于一个矩形而言，它的长设为 $a$，宽设为 $b$，那么我们有恒等式：

$$\frac{a}{b}\geq \frac{b}{a}$$

恒等式看上去好像没有没啥用，但是我们重新考虑 $f(n,a,b,c)$ 的性质：

将 $i$ 视作平面直角坐标系中的 $x$ 坐标，不难发现 $f(n,a,b,c)$ 的含义是：斜率为 $k$ 的过原点直线与 $x$ 正半轴在坐标范围为 $[1,n]$ 时围成的三角形内（上）的整点个数（$x$ 轴上的不算）。

这里有一个变换的过程，考虑将 $n$ 变换成 $k$，缩小 $n$ 的范围。

斜率为 $k$ 的过原点直线与 $x$ 正半轴在坐标范围为 $[1,n]$ 时围成的三角形内（上）的整点个数（$x$ 轴上的不算）等价于：$x$ 范围为 $[1,k]$，$y$ 轴范围为 $[1,n]$ 的矩形（坐标轴边界不算）内的整点数减去斜率为 $k^?$（具体值可以看代码），横坐标范围为 $[1,k]$ 的三角形内的整点数，进而有力地减少了 $n$。

如图所示：

这里应该有一张图。

结论

$$
f(n,a,b,c)=\begin{cases}
0,n=0\\
\frac{n(n+1)\lfloor k\rfloor}{2}+n\lfloor k\rfloor-f(\lfloor k\rfloor,ac,-bc,a^2r-b^2),n\ne 0
\end{cases}
$$

类欧几里得算法的渐进时间复杂度为 $\Theta(\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

int n,r;
double R;

inline ll gcd(reg ll a,reg ll b){
    return b==0?a:gcd(b,a%b);
}

inline ll S(reg int n,reg ll a,reg ll b,reg ll c){
    if(!n)
        return 0;
    reg ll G=gcd(a,gcd(b,c));
    a/=G,b/=G,c/=G;
    reg ll k=(a*R+b)/c;
    reg ll sum=(k*n*(n+1)>>1);
    b-=k*c,k=(a*R+b)/c*n;
    return sum+n*k-S(k,a*c,-b*c,a*a*r-b*b);
}

int main(void){
    reg int T=read();
    while(T--){
        n=read(),r=read();
        R=sqrt(r);
        reg ll T=floor(R);
        if(T*T==r)
            printf("%d\n",T&1?(n&1?-1:0):n);
        else
            printf("%lld\n",n-2*S(n,1,0,1)+4*S(n,1,0,2));
    }
    return 0;
}