题解 SP10395 【ABA12D - Sum of divisors!】

under 题解 SP10395

本文章同步发表于我的博客

solution 1

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

其实这题就是个线筛求 \sigma 的板子。不过求 \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