(未完待续)一道神奇的 类欧几里得算法 题目。
题目链接:Luogu P5172/BZOJ 3817/UOJ 42/清华集训2014 D3T1。
题目
题目描述
$T$ 组数据,给定正整数 $n,r$,求:
$$\sum _ {d=1}^n(-1)^{\lfloor d\sqrt{r}\rfloor}$$
数据范围
变量 | 数据范围 |
---|---|
$n$ | $1\leq n\leq 10^9$ |
$r$ | $1\leq r\leq 10^4$ |
$T$ | $1\leq T\leq 10^4$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
Luogu P5172 | $1\text{s}$ | $250\text{MiB}$ |
BZOJ 3817 | $10\text{s}$ | $256\text{MiB}$ |
UOJ 42 | $1\text{s}$ | $256\text{MiB}$ |
清华集训2014 D3T1 | $1\text{s}$ | $256\text{MiB}$ |
题解
思路
思路其实就是推式子得出来的。
化简式子
$$
\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$,发现:
- 设 $k=\frac{a\sqrt{r}+b}{c}$,则 $f(n,a,b,c)=\sum _ {i=1}^n\lfloor ik\rfloor$。
- 将 $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;
}
近期评论