bzoj 1968: [Ahoi2005]COMMON 约数研究 (思维题)

1968: [Ahoi2005]COMMON 约数研究

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 1997  Solved: 1508
[Submit][Status][Discuss]

Description

Input

只有一行一个整数 N(0 < N < 1000000)。

Output

只有一行输出,为整数M,即f(1)到f(N)的累加和。

Sample Input

3

Sample Output

5

HINT

Source

思路:如果跟着题目的意思走。。。求每个数的约束个数。。。复杂度是不资瓷的。。。

然而因为是求和,我们可以直接考虑,每个因子对答案的贡献。

容易知道,因子x对答案的贡献为n/x

x的范围为1..n

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz