SPOJ 26073 DIVCNT1 - Counting Divisors（SB树上二分折线斜率拟合曲线）

71 阅读 0 评论 47 点赞

我是靠谱客的博主鲜艳白昼，这篇文章主要介绍SPOJ 26073 DIVCNT1 - Counting Divisors（SB树上二分折线斜率拟合曲线），现在分享给大家，希望可以做个参考。

题目
可以看LG的题解
还可以看zzt的论文（但是他好像也没说什么）
其实还是和之前一样，树上二分出当前最优的斜率，然后就按照这个斜率走到不能走，
然后继续二分，用单调栈符合了反比例函数拟合曲线斜率单调的特点，所以可以证明其折线（和二分次数）数量不会太大，为 $O(n^{frac 13})$ ，然后就可以算了。

$A C C o d e$

复制代码

#include<bits/stdc++.h>
#define LL __int128
#define Ct const
#define ll long long
using namespace std;
struct Pt{
LL x,y;Pt(LL x=0,LL y=0):x(x),y(y){}
Pt operator +(Ct Pt &B)Ct{ return Pt(x+B.x,y+B.y); }
}q[5097152],l,r,M;
long long n;
LL m,x,y,cr,ans;
int R;
bool inr(Ct LL &x,Ct LL &y){ return x * y <= n; }
bool inr(Ct Pt &a){ return inr(a.x,a.y); }
int main(){
//	freopen("1.in","r",stdin);
int T;scanf("%d",&T);
for(;T--;){
scanf("%lld",&n);
ans = 0;
m = sqrt(n) , x = n/m , y = m+1 , cr = cbrt(n);
R=0 , q[++R] = Pt(1,0) , q[++R] = Pt(1,1);
for(;y>cr;){
for(l=q[R--];!inr(x+l.x,y-l.y);x+=l.x,y-=l.y) ans += x * l.y + (l.y+1) * (l.x-1) / 2;
if(y<=cr) break;
for(r=q[R];R && inr(x+r.x,y-r.y);l=r,r=q[--R]);
for(;;){
M=l+r;
if(!inr(x+M.x,y-M.y)) q[++R] = r = M;
else{
if(r.y * (x+M.x) * (x+M.x) >= n * r.x) break;
else l = M;
}
}
}
for(y--;y;y--) ans += n / y;
ans = ans * 2 - m * m;
static int q[30];
if(!ans) putchar('0');
for(;ans;) q[++q[0]]=ans%10,ans/=10;
for(;q[0];) putchar('0'+q[q[0]--]);
putchar('n');
}
}

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
#include<bits/stdc++.h>
#define LL __int128
#define Ct const
#define ll long long
using namespace std;
struct Pt{
LL x,y;Pt(LL x=0,LL y=0):x(x),y(y){}
Pt operator +(Ct Pt &B)Ct{ return Pt(x+B.x,y+B.y); }
}q[5097152],l,r,M;
long long n;
LL m,x,y,cr,ans;
int R;
bool inr(Ct LL &x,Ct LL &y){ return x * y <= n; }
bool inr(Ct Pt &a){ return inr(a.x,a.y); }
int main(){
//	freopen("1.in","r",stdin);
int T;scanf("%d",&T);
for(;T--;){
scanf("%lld",&n);
ans = 0;
m = sqrt(n) , x = n/m , y = m+1 , cr = cbrt(n);
R=0 , q[++R] = Pt(1,0) , q[++R] = Pt(1,1);
for(;y>cr;){
for(l=q[R--];!inr(x+l.x,y-l.y);x+=l.x,y-=l.y) ans += x * l.y + (l.y+1) * (l.x-1) / 2;
if(y<=cr) break;
for(r=q[R];R && inr(x+r.x,y-r.y);l=r,r=q[--R]);
for(;;){
M=l+r;
if(!inr(x+M.x,y-M.y)) q[++R] = r = M;
else{
if(r.y * (x+M.x) * (x+M.x) >= n * r.x) break;
else l = M;
}
}
}
for(y--;y;y--) ans += n / y;
ans = ans * 2 - m * m;
static int q[30];
if(!ans) putchar('0');
for(;ans;) q[++q[0]]=ans%10,ans/=10;
for(;q[0];) putchar('0'+q[q[0]--]);
putchar('n');
}
}