题目描述
记 为
的所有真约数（小于
且整除
的正整数）之和。
若 ，则称之为亏数；反之，则称之为盈数。
由于 是最小的盈数，它的真约数之和为
，所以最小的能够表示成两个盈数之和的数是
。通过数学分析可以得出，所有大于
的数都可以被写成两个盈数的和。
求所有不能被写成两个盈数之和的正整数之和。
思路
跟欧拉21 很相似
根据欧拉筛每个合数都被自身最小素因子筛到的特性
结合利用因子和公式，可以在线性时间内求出所有数的因子和
代码
// 素数筛算法求解因子和问题
#include <cstdio>
const int N = 28123;
int prime[N + 5];
int f[N + 5];
int cnt[N + 5]; // cnt[i] 记录 i 最小素因子的幂次
bool mark[N + 5];
void init() {
for (int i = 2; i <= N; i++) {
if (!cnt[i]) { // 如果是合数，则 cnt[i] 已经被标记过
prime[++prime[0]] = i;
f[i] = i + 1;
cnt[i] = i;
}
for (int j = 1; j <= prime[0] && prime[j] * i <= N; j++) {
if (i % prime[j]) { // i 与 prime[j] 互素
cnt[i * prime[j]] = prime[j]; // prime[j] 为 i * prime[j] 的最小素因子
f[i * prime[j]] = f[i] * f[prime[j]];
}
else {
cnt[i * prime[j]] = cnt[i] * prime[j];
f[i * prime[j]] = f[i] * (cnt[i * prime[j]] * prime[j] - 1)
/ (cnt[i * prime[j]] - 1); // 等比数列求和公式
break;
}
}
}
}
int main() {
init();
int k = 0;
for (int i = 2; i <= N; i++) {
if (f[i] > (i << 1)) f[k++] = i;
}
for (int i = 0; i < k; i++) {
for (int j = i; j < k; j++) {
if (f[i] + f[j] > N) break;
mark[f[i] + f[j]] = true;
}
}
int ans = 0;
for (int i = 0; i <= N; i++) {
if (!mark[i]) ans += i;
}
printf("%d\n", ans);
return 0;
}
