AT_abc230_e题解

· · 题解

题解都只写了整除分块算法，这里介绍另外一种做法：

Dirchlet 双曲线法

假设 f=h*g，g,h 是两个积性函数。

那么有 \displaystyle\sum_{i=1}^n f(i)=\sum_{i=1}^n(h*g)=\sum_{xy\le n}h(x)g(y)。

不妨令 G(n)=\displaystyle\sum_{i=1}^n g(i),H(n)=\sum_{i=1}^n h(i)，我们钦定两个数 u,v 满足 uv=n，则有

\begin{aligned}\displaystyle \sum_{i=1}^n f(i)&= \sum_{xy\le n}g(x)h(y)\\ &=\sum_{x\le u,xy\le n}g(x)h(y)+\sum_{u<x\le n,xy\le n}g(x)h(y)\\ &=\sum_{x\le u}g(x)\sum_{y\le n/x}h(y)+\sum_{y\le v}h(y)\sum_{x\le n/y}g(x)-\sum_{x\le u,y\le v} g(x)h(y)\\ &=\sum_{x\le u}g(x)H(n/x)+\sum_{y\le v}h(y)G(n/y)-H(v)G(u) \end{aligned}

当 u=v=\sqrt n 时，不计入 H,G 的计算时间，那么时间复杂度就是 O(\sqrt n)。

这个恒等式我们称之为 Dirichlet 双曲线法，这个式子的三个部分可以被 y=\dfrac{n}{x} 的图像的蓝色，红色，紫色部分所描述。

我们假设 g=h=1，那么 g*h=d，也就是 f=d，通过 Dirchlet 双曲线法，我们可以得到：

\sum_{i=1}^nf(i)=2\sum_{x\le \sqrt n}(n/x)-\lfloor\sqrt n\rfloor^2

对比于整除分块，常数更小，实现也更为简单。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,sq,ans; 
int main(){
    scanf("%lld",&n);
    sq=sqrt(n);
    for(ll i=1;i<=sq;i++) ans+=n/i;
    printf("%lld",ans*2-sq*sq); 
    return 0;
}