数学 - 线性筛带质因数分解

2017/01/16

冬令营上遇到了这样一道题:

有 N 类卡片。每类卡片有若干张。每张卡片上都写了一个数。你要从中选择恰好 K 张卡片。对你选出的每张卡片,设卡片上的数为 x,检查它是否满足以下四种规则: 1. x 是质数; 2. x 的约数的个数是质数; 3. x 的所有约数的和是质数; 4. x 的所有约数的乘积是完全平方数。

每选出一张卡片,这样计算你的得分。若卡片上的数 x 满足规则 i,你的得分就会增加 pi (i = 1…4)。其中 p1…p4 是已知的数。若 x 同时满足多个规则,则分别累加得分。当你选完 K 张卡片后,检查你是否选过满足每种规则的数。若你选的所有卡片上的数都不满足规则 i (i = 1..4),你会得到 ci 的奖励得分。问你能得到的最大和最小得分分别是多少。

先通过做上述四个子任务搞定选每种数的收益,然后贪心搞搞就行。(然而 std 也是这样)

那么就遇到一个问题就是如何写素数筛。

下午讲课环节想到了一种筛法(口胡叫可持久化素数筛),总的来说就是利用欧拉筛每次都是被最小的质因子筛掉,然后就可以向筛掉的方向连一条边,这样就可以构造出一个 DAG。对于每一个数,它的所有质因子按 从小到大排列分布 它到 1 的这条链上。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
const int MAX_N = 2E6 + 1E3;
int isprime[MAX_N]; int sps[MAX_N]; int spspos = 0;
int pren[MAX_N], pred[MAX_N]; // pren: 筛掉它的数, pred: x / pren[x]
void genP() {
    memset(isprime, 0xFF, sizeof(isprime));
    isprime[1] = 0;
    for(int i=2;i<MAX_N;i++) {
        if(isprime[i]) {
            sps[spspos++] = i;
            pren[i] = 1;
            pred[i] = i;
        }

        for(int j=0;j<spspos && i * sps[j] < MAX_N;j++) {
            isprime[i * sps[j]] = 0;
            pren[i * sps[j]] = i;
            pred[i * sps[j]] = sps[j];
            if(i % sps[j] == 0) break;
        }
    }
}

对于这道题的话 1, 2, 4 三个询问都可以很快搞定:

  1. 直接判断质数
  2. 通过因数个数定理( 对于数的质因数幂次表示 ,其因数个数为
  3. 通过 2 里的因数个数两两配对,再特判平方根。