线性筛の应用

注意：线性筛基本可以求出所有积性函数，外层循环都是从2开始的

一、线性筛求质数与欧拉函数

二、线性筛求约数个数

\(设n=\prod_{i=1}^{q}p_i^{r_i}，则约数个数函数fac(n)=\prod_{i=1}^{q}r_i+1，为积性函数（指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数）。辅助数组minp(i)表示i最小质因数的次幂。\)

void Fac(int n) {
    fac[1] = 1, minp[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (!flag[i]) {
            p[++w] = i; fac[i] = 2; minp[i] = 1;
	}
        for (int j = 1; j <= w && i*p[j] <= n;j++) {
            flag[i * p[j]] = 1;
            if (i % p[j] == 0) {
                fac[i * p[j]] = fac[i] / (minp[i] + 1) * (minp[i] + 2);
                minp[i * p[j]] = minp[i] + 1;
                break;
            } else {
                fac[i * p[j]] = fac[i] * 2;
                minp[i * p[j]] = 1;
            }
        }
    }
}

三、线性筛求约数和

\(设n=\prod_{i=1}^{q}p_i^{r_i}，则约数和函数sumd(n)=\prod_{i=1}^{q}\sum_{k=0}^{r_i}p_i^k，为积性函数（指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数）。辅助数组minp(i)表示i最小质因数的次幂。\)

void Sumd(int n) {
    sumd[1] = 1, minp[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (!flag[i]) {
            p[++w] = minp[i] = i; sumd[i] = i + 1
	}
        for (int j = 1; j <= w && i * p[j] <= n; j++) {
            flag[i * p[j]] = 1;
            if(i % p[j] == 0) {
                sumd[i * p[j]] = sumd[i] * (minp[i] * p[j] * p[j] - 1) / (minp[i] * p[j] - 1);
                minp[i * p[j]] = minp[i] * p[j];
                break;
            } else {
                sumd[i * p[j]] = sumd[i] * sumd[p[j]];
                minp[i * p[j]] = p[j];
            }
        }
    }
}

四、线性筛求莫比乌斯函数

默比乌斯函数，也称为莫比乌斯函数、缪比乌斯函数在数论中有着广泛应用。
性质：
\(①\)

\(②对任意正整数n有：\)

void Mu(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!flag[i]) {
            mu[i] = -1; p[++w] = i;
	}
        for (int j = 1; j <= w && i * p[j] <= n; j++) {
            flag[i * p[j]] = 1;
            if (!(i % p[j])) {
                mu[i * p[j]] = 0;
                break;
            } else mu[i * p[j]] = -mu[i];
        }
    }
}

证明自己去查吧（逃

线性筛の应用

原文：https://www.cnblogs.com/zahng/p/15139264.html