CSP-J 2021 初赛 阅读程序 第3题

// 这个程序是欧拉筛
// 历年真题中，考察了 朴素筛、埃式筛法
// 今年，进化到考察 欧拉筛 了

// 时代在进步

// 如果看出来是欧拉筛，那么还有的搞
// 否则，手摸小数据，观察，可能能猜对几个空

// f[i] 表示i的因子个数
// g[i] 表示i的所有因子之和

// b[], c[], d[], 中间变量，感觉很难理解

#include <iostream>
using namespace std;

const int n = 100000;
const int N = n + 1;

int m;
int a[N], b[N], c[N], d[N]; 
int f[N], g[N];

void init()
{
    f[1] = g[1] = 1; 
    for(int i=2;i<=n;i++){
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];


                g[i * k] = g[i] * k + d[i];
                break; }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        } 
    }
}

int main()
{
    init(); 
    int x;
    cin >> x;
    cout << f[x] << ' ' << g[x] << endl;
    return 0;
}

对。后面没用到1，所以，无所谓去掉

对。手摸观察几个小数据，得出规律

错。前面说明了f数组，g数组的作用后，就很明显，两个数组都不是单调递增的。
举反例，g(4)=7, g(5)=6

A。欧拉筛的时间复杂度O(n)

C。f[i]=2，代表i是素数。100以内一共有25个素数。

C。1000 = 2^3 * 5^3， (3+1)*(3+1) = 16，g(1000)=2340

介绍一下，我们线性筛（欧拉筛）的模板

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int primes[N] ,cnt;
bool st[N];  // st[x] 存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

总结

日常学习算法的时候，模板是一个很重要的学习手段，但显然只会模板，只会看模板代码，都会带来不可估量的灾难。