under 题解 SP10395

本文章同步发表于洛谷博客

---

solution 1

首先我们有约数和函数 $\sigma$，它是积性函数，可以用线筛在线性时间内求出，加个前缀和就做完了，总复杂度 $O(\max{B} + T)$，即 $O(n + q)$。

其实这题就是个线筛求 $\sigma$ 的板子。

---

solution 2

不过，抛开这种做法，我们会发现满足要求的数字的一些性质：满足要求的数都是质数的幂，且除 $2$ 外都是平方数。证明在这里

用这两条性质做能做到更小的常数，不过由于上一种做法足够优秀，在此就不讨论了。其实是我看不懂证明

---

code

代码中 s[i] 表示 $\sigma(i)$，ans[i] 表示答案的前缀和。

关于代码中数组的大小这么奇怪的原因就留作习题吧

const int N = 4390848;

std::bitset<4390849> v;
int T, p[308755], s[4390849], ans[1000003];

void sieve_sigma() {
  int M = 0;
  v.set(1), s[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!v[i]) p[++M] = i, s[i] = i + 1;
    for (int j = 1; j <= M && i * p[j] <= N; ++j) {
      v.set(i * p[j]);
      if (i % p[j] == 0) {
        s[i * p[j]] = s[i] + p[j] * (s[i] - s[i / p[j]]);
        break;
      }
      s[i * p[j]] = s[i] * s[p[j]];
    }
  }
  for (int i = 1; i <= 1000000; ++i)
    ans[i] = ans[i - 1] + !v[s[i]];
}

int main() {
  sieve_sigma();
  cin >> T;
  for (int l, r; T; --T) {
    cin >> l >> r;
    cout << ans[r] - ans[l - 1] << '\n';
  }
  cout.flush();
  return 0;
}

---

花絮

这题还是我 半年差一天前（19-08-12）交的翻译来着www

原题中有这么一句话：“如果你真的想通过这道题来学些东西，不要打表！”

但唯一的一篇题解还是裸打表（摊手），所以我就写了这篇题解。

但是写这篇题解真是太棒了，学到许多 /cy