UVa11526 H(n)

链接：Link 耗时：2.232s

分析

粗看题目，不过就是要求这样一个式子：$\sum_{i=1}^n{[\frac{n}{i}]}$的值。但注意到：题目给的数据范围极大，有$2^{31}-1$之多，若遍历计算，则时间复杂度为$O(n)$，将严重超时，不可取。

而事实上，通过尝试我们可以发现：$\sum_{i=1}^{n}{[\frac{n}{i}]}=2*\sum_{i=1}^{\sqrt n}{[\frac{n}{i}]}-{[\sqrt n]}^2$，这是一个重要的结论。因为这条式子一旦成立，时间复杂度即可从$O(n)$降为$O(\sqrt n)$，这是一个极为可观的改善。下面我们来证明一下这个结论：

事实上，

$$ \begin{aligned} \sum_{i=[{\sqrt n}]+1}^{n}{[\frac{n}{i}]} &=1\times(n-[\frac{n}{2}])+2\times([\frac{n}{2}]-[\frac{n}{3}])+\ldots+[\sqrt{n}]\times([\frac{n}{\sqrt{n}}]-{[\frac{n}{\sqrt n}+1]}) \\ &=n+[\frac{n}{2}]+[\frac{n}{3}]+\ldots+[\frac{n}{\sqrt n}]-[\sqrt n]\times[\frac{n}{[\sqrt n]+1}] \\ &=\sum_{i=1}^{[\sqrt n]}{[\frac{n}{i}]}-{[\sqrt n]}^2 \end{aligned}$$

从而，命题得证。

Code

var
    n, _, i: longint;

function h: int64; inline;
var
    k, t: longint;
begin
    h := 0;
    t := trunc(sqrt(n));
    k := 1;
    while k <=t do
    begin
        h := h + n div k;
        inc(k);
    end;
    h := h * 2 - t * t;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(n);
        if n <= 0 then
            writeln(0)
        else
            writeln(h);
    end;

    close(input);
    close(output);
end.

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。