线性筛框架——(算数基本定理、约数个数)-Toy模板网

这篇具有很好参考价值的文章主要介绍了线性筛框架——(算数基本定理、约数个数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算术基本定理

在算术基本定理中，若正整数 $N$ 被唯一分解为 $N=P_1^{c_1}P_2^{c_2}…P_m^{c_m}$ ,其中 $c_i$ 都是正整数， $p_i$ 都是质数，且满足 $p_1<p_2<…<p_m$ ，则 $N$ 的正约数集合可写作： ${P_1^{b_1}P_2^{b_2}…P_m^{b_m}\}$ ，其中 $0\leq b_i\leq c_i$

$N$ 的正约数个数为： $(c_1+1)*(c_2+1)*…*(c_m+1)=\prod\limits_{i=1}^m(c_i+1)$

HDU 1492

题意：给出一个只包含质因数2，3，5，7的数，求其约数的个数

/*************************************************************************
        > File Name: 1492.c
        > Author: Luzelin
        > Mail: 2351767075@qq.com
        > Created Time: Wed Apr  7 20:27:46 2021
 ************************************************************************/

#include <stdio.h>

int main() {
    unsigned long long n;
    while (~scanf("%lld", &n) && n) {
        int a = 1, b = 1, c = 1, d = 1;
        while (n % 2 == 0)  ++a, n /= 2;
        while (n % 3 == 0)  ++b, n /= 3;
        while (n % 5 == 0)  ++c, n /= 5;
        while (n % 7 == 0)  ++d, n /= 7;
        printf("%d\n", a * b * c * d);
    }
    return 0;
}

约数个数

算术基本定理中，根据拆分后的素因子的指数，我们可以求出每个 $N$ 的约数的个数。

根据这个式子，我们可以用线性筛去筛出当前 $N$ 的约数个数。

筛的过程中，我们需要保存下最小素因子的个数。

下面证明中

$an s [i]$ 表示 $i$ 的约数个数

$n u m [i]$ 表示 $i$ 的最小素因子的个数

$p r im e [i]$ 表示第 $i$ 个素数

① 当前数是素数

这种情况我们很容易得到，当前的 $an s [i] = (1 + 1) = 2$ ，

因为素数只有一个素因子(就是它本身)，并且指数为 $1$ 。

而最小素因子个数 $n u m [i] = 1$

② $\ \%\ prime[j]\ \neq \ 0$

这种情况，我们可以知道 $i$ 当中，并不包含 $p r im e [j]$ 这个素因子，然而， $i * p r im e [j]$ 中，包含了一个 $p r im e [j]$

而且由于当前的 $p r im e [j]$ 必然是 $i * p r im e [j]$ 的最小素因子 (因为从小到大枚举啊!)，我们要记录下这个最小素因子的个数

所以保存一个数 $n u m [i * p r im e [j]] = 1$

我们可以从前面得到 $i$ 的所有约数个数 $1+a_1)(1+a_2)…(1+a_n)$

然后再补上当前多了素因子 $p r im e [j]$ 的因子个数 $1+a_1)(1+a_2)…(1+a_n)(1+1)$

所以最后 $an s [i * p r im e [j]] = an s [i] * 2$

③ $i\ \%\ prim[j]\ ==\ 0$

这种情况， $i$ 中必然包含了至少 1 个 $p r im e [j]$ ，而且 $p r im e [j]$ 也必定是 $i$ 的最小素因子，因为每次枚举都是从小的素数开始枚举。

而 $i * p r im e [j]$ 比起 $i$ 则是多了一个最小素因子个数，即 $n u m [i * p r im e [j]] = n u m [i] + 1$

$i$ 的约数个数是 $1+a_1)(1+a_2)…(1+a_n)$

那么 $i * p r im e [j]$ 的约数个数应该是 $1+a_1+1)(1+a_2)…(1+a_n)$

之后，我们就要用到我们之前记录下的最小素因子个数了，因为我们可以知道 $i$ 的最小素因子个数为 $n u m [i]$ ，而 $an s [i]$ 中已经包含了 $1+a_1)(1+a_2)…(1+a_n)$ 这时我们可以除去第一项 $1+a_1$ 然后乘以 $1+a_1+1$ ，就可以得到 $an s [i * p r im e [j]]$ 的约数个数了。 $an s [i * p r im e [j]] = an s [i] / (n u m [i] + 1) * (n u m [i] + 2)$

P1403约数研究

输入一个数n，输出1-n每个数约数的数量和

1   1
2   1 2
3   1 3
4   1 2 4
5   1 5
6   1 2 3 6

input 6
output 14

/*************************************************************************
        > File Name: P1403_1.cpp
        > Author: Luzelin
        > Mail: 2351767075@qq.com
        > Created Time: Fri Apr 29 09:29:54 2022
 ************************************************************************/

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6;

int table[N + 5] = {1, 1}, prime[N + 5], t;
int min_fac_cnt[N + 5], ans[N + 5] = {0, 1};

void make_table() {
    for (int i = 2; i <= N; ++i) {
        if (table[i] == 0) {
            prime[t++] = i;
            min_fac_cnt[i] = 1;
            ans[i] = 2;
        }
        for (int j = 0; i * prime[j] <= N; ++j) {
            table[i * prime[j]] = 1;
            if (i % prime[j]) {
                min_fac_cnt[i * prime[j]] = 1;
                ans[i * prime[j]] = ans[i] * 2;
            } else {
                min_fac_cnt[i * prime[j]] = min_fac_cnt[i] + 1;
                ans[i * prime[j]] = ans[i] / (min_fac_cnt[i] + 1) * (min_fac_cnt[i] + 2);
                break;
            }
            // if (i % prime[j] == 0)  break;
        }
    }
    return ;
}

int main() {
    make_table();
    for (int i = 2; i <= N; ++i) {
        ans[i] += ans[i - 1];
    }
    int n;
    cin >> n;
    cout << ans[n] << endl;
    return 0;
}

优化空间版：文章来源地址https://www.toymoban.com/news/detail-403609.html

/*************************************************************************
        > File Name: P1403.cpp
        > Author: luzelin
        > Mail: luzelin1024@163.com
        > Created Time: Sun 30 Oct 2022 04:08:08 PM CST
 ************************************************************************/

#include <iostream>

using namespace std;

const int N = 1e6;

// fc : factor cnt    mfc : min factor cnt
int fc[N + 5] = {0, 1}, mfc[N + 5] = {1, 1}, table[N + 5];

void make_table(int n) {
    for (int i = 2; i <= n; ++i) {
        if (table[i] == 0) {
            table[++table[0]] = i;
            fc[i] = 2;
            mfc[i] = 1;
        }
        for (int j = 1; i * table[j] <= n; ++j) {
            table[i * table[j]] = 1;
            if (i % table[j]) {
                fc[i * table[j]] = fc[i] << 1;
                mfc[i * table[j]] = 1;
            } else {
                fc[i * table[j]] = fc[i] / (mfc[i] + 1) * (mfc[i] + 2);
                mfc[i * table[j]] = mfc[i] + 1;
                break;
            }
        }
    }
    return ;
}

int GetAns(int n) {
    make_table(n);
    for (int i = 2; i <= n; ++i)  fc[i] += fc[i - 1];
    return fc[n];
}

int main() {
    int n;
    cin >> n;
    cout << GetAns(n) << endl;
    return 0;
}