python/TangDou/AcWing/DP/Tree/Euler_YueShuSum.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e3 + 10;

int primes[N], cnt;
bool st[N];

int num[N]; //最小质因子p1组成的等比序列 p1^0+p1^1+...+p1^r1
int sd[N]; //约数和

int n;

void get_primes(int n) {
    sd[1] = 1; // 1的约数只有自己，约数和是1

    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            //质数
            sd[i] = num[i] = i + 1; // 1和自身是约数，约数和为i+1; 同时因为i是质数，所以只有一个分拆项,并且分拆项内容=pj^0+pj^1=1+pj=1+i
        }
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;

            if (i % primes[j]) {
                sd[i * primes[j]] = sd[i] * sd[primes[j]]; //积性函数
                num[i * primes[j]] = primes[j] + 1;
            } else {
                sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
                num[i * primes[j]] = num[i] * primes[j] + 1;
                break;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    get_primes(n);
    //约数和要不要自己本身,这里是不想要自己本身
    for (int i = 1; i <= n; i++) printf("%d ", sd[i] - i);
    puts("");
    return 0;
}