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

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

$\mathrm{A}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{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');
}
}

最后

以上就是鲜艳白昼为你收集整理的SPOJ 26073 DIVCNT1 - Counting Divisors（SB树上二分折线斜率拟合曲线）的全部内容，希望文章能够帮你解决SPOJ 26073 DIVCNT1 - Counting Divisors（SB树上二分折线斜率拟合曲线）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。