0%

HYSBZ 1968：约数研究

发表于 分类于 Valine：

约数之和 => 倍数之和

题目链接

https://vjudge.net/problem/HYSBZ-1968

题意

定义\(f(n)\)为整数\(n\)的因数的个数。现输入一个N，求\(\sum_{i=1}^N{f(i)}\)。

数据范围：\(0<N<10^6\)

我的失败尝试

直接想把1~1000000的直接初始化出来，于是直接写成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
ll sum[MAX + 5];
int f[MAX + 5];
void init() {
    memset(f, 0, sizeof(f));
    sum[0] = 0;
    for (int i = 1; i < MAX; i++) {
        for (int j = i; j < MAX; j += i) {
            f[j]++;
        }
        sum[i] = sum[i - 1] + f[i];
    }
}

算了算复杂度好像是\(O(N\cdot log\ N)\)的，以为能过，结果T了。

题解

题目要求[1, N]范围内所有数的因数个数之和。分析可得：对任意一个在[1, N]范围内的数，因数都在[1, N]范围内

因此，[1, N]范围内所有数的因数个数之和可以转化为[1, N]范围内所有数的在[1, N]范围的倍数的个数之和。

那么对于任意\(i\in [1,N]\)，i在[1, N]范围内的倍数个数为:\(\lfloor \frac N i \rfloor\)。则容易得到最终的解如下：

\[ \sum_{i=1}^N{f(i)}=\sum_{i=1}^N\lfloor \frac N i \rfloor \]

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    scanf("%d", &N);
    ll res = 0;
    for (int i = 1; i <= N; i++) {
        res += N / i;
    }
    printf("%lld\n", res);
    return 0;
}