P1403. 约数研究

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 153 阅读时长 ≈ 1 分钟

考点

  • 枚举约数

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, ans, cnt[LEN];

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; j += i) {
      ++cnt[j];
    }
  }
  for (int i = 1; i < LEN; ++i) ans += cnt[i];
  cout << ans;
  return 0;
}

思路

求每个数\(n\)的约数个数，不可能一个个遍历到\(\sqrt{n}\)，总的复杂度高达\(O\left( n\sqrt{n} \right)\)

可以让每个数告诉自己的倍数，“我是你的因数”，这样总的复杂度只有\(O\left( \sum{\begin{array}{c} n\\ i=1\\ \end{array}\frac{n}{i}} \right)\)，调和级数

接近\(O\left( n\log n \right)\)