题解 SP26073 【DIVCNT1 - Counting Divisors】

x义x · 2020-07-20 10:56:45 · 题解

可能更好的阅读体验

首先把式子转化为

设 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) 的优异复杂度。

还有一些细节：

• 为了方便可以改为存向量的绝对值。（真的方便吗？）

代码：

#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");
    }
}