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.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。

«Sublime configuration for Pascal

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.