SP26073 DIVCNT1 - Counting Divisors
前置知识:Stern-Brocot 树。
本文中,定义曲线上的点位于曲线下方。
思路
首先:
其中
考虑
图中区域 A(不含坐标轴)内的整点数量即为
然而区域 A 内的整点数量无法直接计算。考虑化曲为直,构造一个所有顶点均为整点的凸包,使得区域 B 内的所有整点均在凸包内或凸包的边上,且凸包内不含曲线下方的点。
接下来考虑如何计算凸包左下方每条边对答案的贡献。
设边的两端分别为
左侧矩形内的整点数量为
右侧三角形中只有
设多边形内部与边界的整点数之和为
则
对于右侧三角形,其面积
:::info[为什么
平行于
将其相加。三角形的顶点均被计算了两次,于是总整点数
之后我们会讲到,
:::
代入,得
矩形右边界上的
设总整点数为
接下来考虑如何构造凸包。
从
::::info[为什么从
注意到区域 B 内横坐标最小的整点
从
:::info[合法性]{open}
首先
其中
显然有
因此
:::
::::
设当前位于
可以证明凸包左下方每一条边的斜率
设
我们需要找到一个最大的既约分数
不难想到二分查找
考虑在 Stern-Brocot 树上二分。初始时
设当前
设中间向量
根据 Stern-Brocot 树的性质,
若
否则令
考虑二分的终止条件。
曲线的函数表达式为
当
思考一下,若每次二分都要从
考虑优化。开一个存储向量的单调栈,向量斜率的绝对值从栈底到栈顶单调递增。
初始时,往栈中先后加入
每次从
若
设当前栈顶为
若
然后在
当
时间复杂度为
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;
}
参考文献
本文还参考了一些资料
[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.