SP26073 DIVCNT1 - Counting Divisors

· · 题解

前置知识:Stern-Brocot 树。

本文中,定义曲线上的点位于曲线下方。

思路

首先:

S_1(n)=\sum\limits_{i=1}^{n}\sigma_0(i)=\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=2\sum\limits_{i=1}^{m}\lfloor\frac{n}{i}\rfloor-m^2.

其中 m=\lfloor\sqrt{n}\rfloor。

考虑 \displaystyle{\sum\limits_{i=1}^{m}\lfloor\frac{n}{i}\rfloor} 的几何意义。

图中区域 A(不含坐标轴)内的整点数量即为 \displaystyle{\sum\limits_{i=1}^{m}\lfloor\frac{n}{i}\rfloor}。

然而区域 A 内的整点数量无法直接计算。考虑化曲为直,构造一个所有顶点均为整点的凸包,使得区域 B 内的所有整点均在凸包内或凸包的边上,且凸包内不含曲线下方的点。

接下来考虑如何计算凸包左下方每条边对答案的贡献。

设边的两端分别为 (x,y) 与 (x+p,y-q)。

左侧矩形内的整点数量为 xq(左边界为坐标轴,上边界已统计过)。

右侧三角形中只有 (x,y) 与 (x+p,y-q) 两个点不在曲线下方。根据 Pick 定理,对于一个顶点坐标均为整点的简单多边形,其面积 A 与内部整点数 i、边界整点数 b 存在如下关系:

A=i+\frac{b}{2}-1.

设多边形内部与边界的整点数之和为 N。

则 N=i+b=A-\dfrac{b}{2}+1+b=A+\dfrac{b}{2}+1.

对于右侧三角形,其面积 A=\dfrac{1}{2}pq,边界整点数 b=p+q+1。

:::info[为什么 b=p+q+1?]{open}

平行于 x 轴的直角边上有 p+1 个整点,平行于 y 轴的直角边上有 q+1 个整点,斜边上有 \gcd(p,q)+1 个整点。

将其相加。三角形的顶点均被计算了两次,于是总整点数 b=p+1+q+1+\gcd(p,q)+1-3=p+q+\gcd(p,q)。

之后我们会讲到,\dfrac{q}{p} 是 Stern-Brocot 树上的分数,满足 \gcd(p,q)=1。故 b=p+q+1。

:::

代入,得 N=\dfrac{1}{2}(pq+p+q+1)+1。

矩形右边界上的 q 个点与三角形边界重合。(x,y) 与 (x+p,y-q) 两个点在曲线上方。

设总整点数为 N',则:

N'&=xq+\frac{1}{2}(pq+p+q+1)+1-q-2\\ &=xq+\frac{1}{2}(pq+p-q-1)\\ &=xq+\frac{1}{2}(p-1)(q+1). \end{aligned}

接下来考虑如何构造凸包。

从 (\lfloor\dfrac{n}{m}\rfloor,m+1) 开始。

::::info[为什么从 (\lfloor\dfrac{n}{m}\rfloor,m+1) 开始?]{open}

注意到区域 B 内横坐标最小的整点 (\lfloor\dfrac{n}{m}\rfloor+1,m) 必然是凸包的顶点。

从 (\lfloor\dfrac{n}{m}\rfloor,m+1) 开始,可以简化计算。从凸包左下方第一条边开始就无需计算左侧矩形上边界上的整点,且第一条边(顶点分别为 (\lfloor\dfrac{n}{m}\rfloor,m+1) 与 (\lfloor\dfrac{n}{m}\rfloor+1,m))斜率为 -1。

:::info[合法性]{open}

首先 \lfloor\dfrac{n}{m}\rfloor\times(m+1)=\lfloor\dfrac{n}{m}\rfloor\times m+\lfloor\dfrac{n}{m}\rfloor,而 n=\lfloor\dfrac{n}{m}\rfloor\times m+(n \bmod m)。

其中 \lfloor\dfrac{n}{m}\rfloor=\lfloor\dfrac{n}{\sqrt{n}}\rfloor\ge\sqrt{n},(n \bmod m)=(n \bmod \lfloor\sqrt{n}\rfloor)<\lfloor\sqrt{n}\rfloor。

显然有 \lfloor\dfrac{n}{m}\rfloor>(n \bmod m)。

因此 \lfloor\dfrac{n}{m}\rfloor\times(m+1)>n,即 (\lfloor\dfrac{n}{m}\rfloor,m+1) 在曲线上方。

:::

::::

设当前位于 (x,y)。

可以证明凸包左下方每一条边的斜率 -\dfrac{q}{p} 都在 [-1,0) 范围内。

设 \boldsymbol{h}(p,q)=(p,-q),其中 (p,-q) 为向量。

我们需要找到一个最大的既约分数 \dfrac{q}{p},使得 (x,y)+\boldsymbol{h}(p,q) 在曲线上方。

不难想到二分查找 \dfrac{q}{p}。然而,若直接对实数进行二分,无法对应 p,q。

考虑在 Stern-Brocot 树上二分。初始时 \boldsymbol{L}\gets \boldsymbol{h}(1,1),\boldsymbol{R}\gets \boldsymbol{h}(1,0),分别对应斜率 -1 与 0。

设当前 \boldsymbol{L}=\boldsymbol{h}(x_L,y_L),\boldsymbol{R}=\boldsymbol{h}(x_R,y_R)。

设中间向量 \mathbf{mid}=\boldsymbol{h}(x_{\mathrm{mid}},y_{\mathrm{mid}})。

根据 Stern-Brocot 树的性质,x_{\mathrm{mid}}=x_L+x_R,y_{\mathrm{mid}}=y_L+y_R,即 \mathbf{mid}=\boldsymbol{L}+\boldsymbol{R}。

若 (x,y)+\mathbf{mid}=(x+x_{\mathrm{mid}},y-y_{\mathrm{mid}}) 在曲线上方,则令 \boldsymbol{R}\gets\mathbf{mid}。

否则令 \boldsymbol{L}\gets\mathbf{mid}。继续二分。

考虑二分的终止条件。

曲线的函数表达式为 f(x)=\dfrac{n}{x},其导数为 f'(x)=-\dfrac{n}{x^2}。

当 (x,y)+\mathbf{mid} 在曲线下方时,若 -\dfrac{y_R}{x_R}\le f'(x+x_{\mathrm{mid}}),即 (x+x_{\mathrm{mid}})^2 y_R\ge nx_R,则之后二分到的点无论如何都会在曲线下方,此时应终止二分。而 \boldsymbol{R} 就是我们要找的 \boldsymbol{h}(p,q)。

思考一下,若每次二分都要从 \boldsymbol{L}=\boldsymbol{h}(1,1),\boldsymbol{R}=\boldsymbol{h}(1,0) 开始,复杂度无法接受。

考虑优化。开一个存储向量的单调栈,向量斜率的绝对值从栈底到栈顶单调递增。

初始时,往栈中先后加入 \boldsymbol{h}(1,0) 与 \boldsymbol{h}(1,1)。

每次从 (x,y) 开始时,先取出栈顶向量(也就是上一步找到的可行的向量),记为 \boldsymbol{l}。

若 (x,y)+\boldsymbol{l} 在曲线上方,则令 (x,y)\gets(x,y)+\boldsymbol{l} 并计算贡献,继续判断新的 (x,y)+\boldsymbol{l} 是否在曲线上方;否则退出循环。

设当前栈顶为 \boldsymbol{r}。

若 (x,y)+\boldsymbol{r} 在曲线下方,则令 \boldsymbol{l}\gets \boldsymbol{r},进行弹栈,并令 \boldsymbol{r} 为新的栈顶,继续判断新的 (x,y)+\boldsymbol{r} 是否在曲线下方;否则退出循环。

然后在 \boldsymbol{l} 与 \boldsymbol{r} 之间二分即可。二分过程中,若 (x,y)+\mathbf{mid} 在曲线上方,则将 \mathbf{mid} 加入单调栈。

当 y\le n^{\frac{1}{3}} 时直接暴力。

时间复杂度为 \mathcal{O}(n^{\frac{1}{3}} \log n) ^{\textup{\textmd{\textsf{[1]}}}}。

Code

注意开 __int128。

#include<bits/stdc++.h>
#define int long long
#define lint __int128

using namespace std;

int T,n;

lint ans;

struct vec{
    int x,y;
};

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

inline void write(lint x){
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}

int _sqrt(int x){
    int ret=floor(sqrtl(x));
    while((ret+1)*(ret+1)<=x)ret++;
    return ret;
}

bool _chk(int x,int y){
    return (lint)x*y>(lint)n;
}

int _calc(int x,int p,int q){
    return x*q+(p-1)*(q+1)/2;
}

void _solve(){
    n=read();
    ans=0;
    int m=_sqrt(n);
    int X=n/m,Y=m+1;
    stack<vec>s;
    while(!s.empty())s.pop();
    s.push((vec){1,0}),s.push((vec){1,1});
    while(1){
        vec l=s.top();
        s.pop();
        while(_chk(X+l.x,Y-l.y)){
            ans+=(lint)_calc(X,l.x,l.y);
            X+=l.x,Y-=l.y;
        }
        if((lint)Y*Y*Y<=(lint)n)break;
        vec r=s.top();
        while(!_chk(X+r.x,Y-r.y)){
            l=r;
            s.pop();
            r=s.top();
        }
        while(1){
            vec mid=(vec){l.x+r.x,l.y+r.y};
            if(_chk(X+mid.x,Y-mid.y)){
                r=mid;
                s.push(r);
            }else{
                if((lint)(X+mid.x)*(X+mid.x)*r.y>=(lint)n*r.x)break;
                else l=mid;
            }
        }
    }
    for(int i=1;i^Y;i++)ans+=(lint)(n/i);
    ans=ans*2-(lint)m*m;
    write(ans);
    printf("\n");
}

signed main(){
    T=read();
    while(T--)_solve();
    return 0;
}

参考文献

本文还参考了一些资料 ^{\textup{\textmd{\textsf{[2-4]}}}}。

[1] 朱震霆. 一些特殊的数论函数求和问题[C]//张瑞喆. IOI2018 中国国家候选队论文集. 2018: 92-112.

[2] Sladkey R. A Successive Approximation Algorithm for Computing the Divisor Summatory Function (draft)[EB/OL]. (2024-11-27)[2025-12-19]. https://arxiv.org/pdf/1206.3369.

[3] Leasier. 题解 SP26073 【DIVCNT1 - Counting Divisors】[EB/OL]. (2024-08-29)[2025-12-19]. https://www.luogu.com.cn/article/k6rvb2tf.

[4] Achtoria. SP26073 DIVCNT1 - Counting Divisors[EB/OL]. (2021-12-10)[2025-12-19]. https://www.cnblogs.com/Go7338395/p/15672217.html.