# 洛谷-P1403

## 题目描述

$$\sum_{i=1}^n f(i)$$

## 样例 #1

### 样例输入 #1

3


### 样例输出 #1

5


## 提示

• 对于 $20%$ 的数据，$N \leq 5000$；
• 对于 $100%$ 的数据，$1 \leq N \leq 10^6$

## 思路

### 最简单的暴力

long int answer = 1;
for (int n = 2;n <= target;n++) {
for (int k = 1;k <= n;k++) {
}
}


### 筛法

long int *divisorNum = new long int[n];
assert(divisorNum);

for (int i = 2;i <= target;i++) {
answer += divisorNum[i] + 2;	// 1 和它本身
for (int times = i;i <= target;times += i)
divisorNum[times]++;
}


### 数学法

From the description of $f(i)$,we could rewrite it as $$f(i) = \sum ^{i} _{k = 1} [k | i]$$

Here,$a | b$ meas that a is a divisor of b.

The mark,$[ cond ]$,introduced in Iverson's APL and used widely in Concrete Mathematics,means $$[cond] = \begin{cases} 1 & \text{if cond is true} \\ 0 & \text{else} \end{cases}$$

Our answer is $\sum _{d = 1} ^{d} f(d)$,which is equal to $$\sum _{d = 1} ^{n} \sum _{k = 1} ^{d} [k | d]$$ then $$\sum _{d = 1} ^{n} \sum _{k = 1} ^{n} [k | d]$$

The reason is that any number larger than k could not be k's divisor. This change removes dependency of d in the inner summary,which makes the next step easier.

Exchange the order to make it clearer $$\sum _{k = 1} ^{n} \sum _{d = 1} ^{n} [k | d]$$

The problem,now,is transformed into that the number of multiples of k between 1 and n.

This could be easily done.The answer is $\lfloor \frac n k \rfloor$.

So we just need to compute $$\sum _{k = 1} ^{n} \lfloor \frac n k \rfloor$$

Last Change: 2022-08-06

GO BACK