0%

SPOJ26073 题解 - DIVCNT1

题目链接

首先把式子转化为

设 $B=\lfloor\sqrt n\rfloor$。则显然有原式等于

考虑

也就是 $xy\le n,x>0,y>0,y\le B$ 内部的整点数,记这个区域为 $R$。这里贺一张著名图片。

总的思路就是用一系列 $x,y$ 都是整数的向量拼接起来,去拟合这个函数。为了能构造出任意斜率的向量来完美拟合,我们需要 Stern-Brocot Tree

我们需要一个单调栈,里面的向量斜率单调降。设当前坐标为 $(x,y)$。算法流程如下:

  • 取出栈顶向量弹出,不断加上它,直到还差一步就会走进 $R$。

    • 每走一步都可能带来一些贡献。如图,贡献是 $xv+(v+1)(u-1)/2$。(皮克定理)

  • 不断弹出栈顶,直到加上栈顶刚好走不进 $R$,称它为 $r$。设最近一次弹的是 $l$(它也有可能是上一步的栈顶向量)。现在的情况是,加上 $l$ 刚好走进 $R$,加上 $r$ 刚好走不进 $R$。

  • 开始二分,用 Stern-Brocot Tree 搞出一个 $l,r$ 的中间向量,也就是 $(l_x+r_x,l_y+r_y)$ 称为 $mid$。

    • 如果 $mid$ 走一步不会进 $R$,那么 $mid$ 进栈并把 $r\leftarrow mid$ 继续二分。
    • 否则,
      • 如果 $r\le f’(x+x_{mid})$,那么如果继续二分就会找不到任何一步不进 $R$ 的向量,直接停止二分。

      • ↑ 可以发现如果 $r\le f’(x+x_{mid})$,$mid,r$ 的中间向量 $midmid$ 显然一步进 $R$,而且因为 $f’$ 单调增,$r\le f’(x+x_{midmid})$ 也一定满足……进入了死结。
      • 否则 $l\leftarrow mid$ 继续二分。

当 $y\le \sqrt[3] n$ 时可以直接暴力。可以证明这样就获得了 $O(\sqrt[3]n\log n)$ 的优异复杂度。

还有一些细节:

  • $(x,y)$ 从 $(\lfloor\dfrac{n}{B}\rfloor,B+1)$ 开始。可以发现所用斜率必然是 $[-1,0]$ 之间,于是栈里初始化为 $(1,0),(1,1)$。

  • 为了方便可以改为存向量的绝对值。(真的方便吗?)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;

void myw(lll x){
if(!x) return;
myw(x/10);printf("%d",(int)(x%10));
}

struct vec{
ll x,y;
vec (ll x0=0,ll y0=0){x=x0,y=y0;}
vec operator +(const vec b){return vec(x+b.x,y+b.y);}
};

ll N;
vec stk[1000005];int len;
vec P;
vec L,R;

bool ninR(vec a){return N<(lll)a.x*a.y;}
bool steep(ll x,vec a){return (lll)N*a.x<=(lll)x*x*a.y;}

lll Solve(){
len=0;
ll cbr=cbrt(N),sqr=sqrt(N);
P.x=N/sqr,P.y=sqr+1;
lll ans=0;
stk[++len]=vec(1,0);stk[++len]=vec(1,1);
while(1){
L=stk[len--];
while(ninR(vec(P.x+L.x,P.y-L.y)))
ans+=(lll)P.x*L.y+(lll)(L.y+1)*(L.x-1)/2,
P.x+=L.x,P.y-=L.y;
if(P.y<=cbr) break;
R=stk[len];
while(!ninR(vec(P.x+R.x,P.y-R.y))) L=R,R=stk[--len];
while(1){
vec mid=L+R;
if(ninR(vec(P.x+mid.x,P.y-mid.y))) R=stk[++len]=mid;
else if(steep(P.x+mid.x,R)) break;
else L=mid;
}
}
for(int i=1;i<P.y;i++) ans+=N/i;
return ans*2-sqr*sqr;
}

int T;

int main(){
scanf("%d",&T);
while(T--){
scanf("%lld",&N);
myw(Solve());printf("\n");
}
}