【洛谷P6028】算术 | Mrsrz's blog

数论。

题目大意：

令 $n$ 的质因数分解结果为 $\prod\limits_{i=1}^k p_i^{\alpha_i}$，我们定义函数 $f(n)$。

$$f(n)=\prod_{i=1}^k\frac{p_i^{\alpha_i+1}-1}{p_i^{\alpha_i+1}-p_i^{\alpha_i}}$$

给定 $N$，求 $\sum\limits_{i=1}^N f(i)$。

题解：

我不会近似，我不会整除分块，我只会枚举。

考虑转化一下 $f(n)$。

$$f(n)=\prod_{i=1}^k\frac{p_i^{\alpha_i+1}-1}{p_i^{\alpha_i+1}-p_i^{\alpha_i}}\\ =\prod_{i=1}^k\frac{(p_i-1)\sum_{j=0}^{\alpha_i}p_i^{j}}{p_i^{\alpha_i}(p_i-1)}\\ =\frac{\prod_{i=1}^k\sum_{j=0}^{\alpha_i}p_i^{j}}{\prod_{i=1}^k p_i^{\alpha_i}}\\ =\frac{\sigma(n)}{n}$$

其中 $\sigma(n)$ 等于 $n$ 的所有正因数的和。

所以我们要求的是 $\sum\limits_{i=1}^N \frac{\sigma(i)}i$ 的值。

我们考虑对每个因数计算贡献。

对于一个数 $n$，若其有因子 $k$，则必有因子 $\frac{n}k$。若 $k\lt \sqrt n$，则 $\frac n k\gt \sqrt n$。当然有 $k=\frac n k=\sqrt n$ 的情况，此时只能计算一次。

那么我们对因数 $k$，分成 $k\leq \sqrt n$ 和 $k\gt \sqrt n$ 来计算贡献。

我们先计算 $k\leq \sqrt n$ 的情况，可知这样的 $k$ 不超过 $\sqrt N$ 个。

枚举 $k$，对于一个 $k$，为了使它的贡献满足 $k\leq \sqrt n$，所以我们只计算在 $[k^2,N]$ 中 $k$ 的贡献。它的贡献为：

$$k\cdot\sum_{i=k}^{\lfloor\frac N k\rfloor}\frac1{ik}=\sum_{i=k}^{\lfloor\frac N k\rfloor}\frac1{i}$$

令函数 $g(n)=\sum\limits_{i=1}^n \frac 1 i$，则这部分贡献可以表示为 $g(\lfloor\frac N k\rfloor)-g(k-1)$。

这里的 $g(n)$ 是调和级数，当 $n$ 非常大时，其近似为 $\ln n+\gamma$，其中 $\gamma\approx 0.5772156649$，所以预处理 $n$ 较小的时候的值，$n$ 较大的时候用 $\ln n+\gamma$ 计算，即可 $O(1)$ 计算单个的贡献。

接着计算 $k\gt \sqrt n$ 的情况，这样的 $k$ 满足 $\lfloor\frac N k\rfloor$ 不超过 $\sqrt N$ 个。

枚举 $\lfloor\frac N k\rfloor$，令其为 $x$，我们对每个 $x$ 的倍数 $n$，计算 $\frac n x$ 的贡献。

为了使这里的贡献满足 $\frac n x \gt\sqrt n$，对于 $x$ 只计算 $(x^2,N]$ 的贡献。

所以对于一个 $x$，它的贡献为：

$$\sum_{i=x}^{\lfloor\frac N x\rfloor}\frac{ix}{x}\cdot\frac{1}{ix}=\frac{\lfloor\frac N x\rfloor-x}x$$

这显然可以 $O(1)$ 计算。

我们计算每部分贡献，枚举的数都是 $\sqrt N$ 个，所以时间复杂度 $O(\sqrt N)$。

于是我们使用了枚举算法解决此题。

Code：

#include<cstdio>
#include<cmath>
typedef long long LL;
LL n;
double Ln[55],ans;
inline double ln(LL x){return x<51?Ln[x]:log(x)+0.5772156649;}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=50;++i)Ln[i]=Ln[i-1]+1./i;
    for(int i=1;(LL)i*i<=n;++i)ans+=ln(n/i)-ln(i-1)+1.*(n/i-i)/i;
    printf("%f\n",ans);
    return 0;
}