题解 SP10395 【ABA12D - Sum of divisors!】
fa_555
2020-02-11 20:28:56
under 题解 [SP10395](https://www.luogu.com.cn/problem/SP10395)
本文章同步发表于[我的博客](https://fa555.github.io/2020/题解-SP10395-ABA12D-Sum-of-divisors/)
---
#### solution 1
首先我们有约数和函数 $\sigma$，它是**积性函数**，可以用线筛在线性时间内求出，加个前缀和就做完了，总复杂度 $O(\max{B} + T)$，即 $O(n + q)$。
其实这题就是个线筛求 $\sigma$ 的板子。不过求 $\sigma$ 的代码实现值得一学。
---
#### solution 2
不过，抛开这种做法，我们会发现满足要求的数字的一些性质：**满足要求的数都是质数的幂，且除 $2$ 外都是完全平方数。**[证明在这里](http://oeis.org/A000203)
用这两条性质做能做到更小的常数，不过由于上一种做法足够优秀，在此就不讨论了。~~其实是我看不懂证明~~
---
#### code
代码中 `s[i]` 表示 $\sigma(i)$，`ans[i]` 表示答案的前缀和。
~~关于代码中数组的大小这么奇怪的原因就留作习题吧~~
``` cpp
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