三、完善程序题（第 19—20 大题，共 10 个小题，30 分）

完善程序（区间不完美度之和）

题目描述

如果一个数等于它的所有因数（小于自身的）之和，那么这个数就是完美的。例如，28 是完美的，因为 $28=1+2+4+7+14$。基于这个定义，我们将数字 $n$ 的不完美度定义为 $f(n)$，它等于 $n$ 与 $n$ 的所有因数（小于 $n$ 的）之和的差的绝对值，因此完美数的不完美度为 0，其余自然数的不完美度都大于 0。

例如：

$f(6)=|6-(1+2+3)|=0$

$f(11)=|11-1|=10$

$f(24)=|24-(1+2+3+4+6+8+12)|=12$

写一个程序，对于正整数 $A$ 和 $B$，计算 $A$ 和 $B$ 之间所有数字不完美度之和，即 $f(A)+f(A+1)+\cdots+f(B)$。

输入描述

第一行输入包含两个整数 $A$ 和 $B$（$1\le A\le B\le 10^7$），表示题目中的 $A$ 和 $B$。

输出描述

输出一个整数，表示 $f(A)+f(A+1)+\cdots+f(B)$。

输入样例 #1

1 9

输出样例 #1

21

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e7 + 5;
LL ans;
int a, b, len;
int prim[N], psum[N], s[N];
bool vis[N];
void sieve(int x) {
    for (int i = 2; ①; i++) {
        if (!vis[i]) {
            prim[++len] = ②;
            psum[i] = s[i] = ③;
        }
        for (int j = 1; j <= len && i * prim[j] <= x; j++) {
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0) {
                psum[i * prim[j]] = ④;
                s[i * prim[j]] = s[i] / psum[i] * psum[i * prim[j]];
                break;
            }
            psum[i * prim[j]] = prim[j] + 1;
            s[i * prim[j]] = s[i] * psum[i * prim[j]];
        }
    }
}
int main() {
    scanf("%d%d", &a, &b);
    sieve(max(a, b));
    s[1] = 1;
    for (int i = a; i <= b; i++)
        ans += abs(s[i] - ⑤);
    printf("%lld\n", ans);
    return 0;
}

②处应填（ ）。

{{ select(1) }}

• psum[i]
• i
• s[i]
• i+1