筛质数

欧拉筛：让每一个合数只被它的最小质因子筛掉，这样每个合数只会被筛一次，时间复杂度 $O(n)$。对于遍历到的素数 $p$，$p|x$ 时停止遍历，对 $x=pr$ ($p>r$，其中 $p$ 是 $x$ 的最小质因数)，对于 $p^\prime>p$，$p^\prime x=pp^\prime r=p(p^\prime r)$，说明 $p^\prime r$ 最小质因数不是 $p^\prime$。

1292. 哥德巴赫猜想

题意：对偶数 $6\le n<10^6$，输出满足 $n=a+b$ 且 $b-a$ 最大的一组奇素数 $a,b$。

  线性筛后，遍历找到第一个满足 $n-p$ 也是素数的 $p$ 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;

vector<int> p;
int v[N];

void sieve(int _) {
    for (int i = 2; i <= _; ++i) {
        if (!v[i]) p.push_back(i);
        for (int j : p) {
            if (i * j > _) break;
            v[i * j] = 1;
            if (i % j == 0) break;
        } 
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve(N - 5);
    int n;
    while (cin >> n && n) {
        for (int i = 0; i <= (int)p.size(); ++i) {
            if (!v[n - p[i]]) {
                cout << n << " = " << p[i] << " + " << n - p[i] << "\n";
                break;
            }
        }
    }
    return 0;
}

1293. 夏洛克和他的女朋友

题意：对序列 $2,3,\dots n + 1$ 染色，使得质因子颜色不同，要求颜色最少。

  构造，$n\ge3$ 最少为 2，质数为 1，合数为 2。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n; n++;
    vector<int> v(n + 1), p;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) p.push_back(i);
        for (int j : p) {
            if (i * j > n) break;
            v[i * j] = 1;
            if (i % j == 0) break;
        }
    }
    cout << (n > 3 ? 2 : 1) << "\n";
    for (int i = 2; i <= n; ++i) {
        cout << (v[i] ? 2 : 1) << " \n"[i == n];
    }
    return 0;
}

分解质因数

197. 阶乘分解

题意：整数 $3\le n\le10^6$，阶乘 $n!$ 按算术基本定理分解输出 $p_i$ 和 $c_i$。

  legendre 定理，$r(n!)=\lfloor n/p\rfloor + r(\lfloor n/p\rfloor!)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n + 1), p;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) p.push_back(i);
        for (int j : p) {
            if (i * j > n) break;
            v[i * j] = 1;
            if (i % j == 0) break;
        }
    }
    for (int i : p) {
        int tmp = n, c = 0;
        while (tmp) {
            c += tmp / i;
            tmp /= i;
        }
        cout << i << " " << c << "\n";
    }
    return 0;
}

概论与数学期望

217. 绿豆蛙的归宿

题意：求有向无环图中起点到终点总长度期望值，在每个顶点访问每条边概率为该点出度倒数。

  利用期望的线性性质：$\mathbb{E}(aX+bY)=a\mathbb{E}(X)+b\mathbb{E}(Y)$，利用记忆化 dp 递推求解即可，f[i] 表示从顶点 i 到终点的期望，状态转移方程如下。

$$f[v]=\sum_{i=1}^k\frac{1}{k}(w[i]+f[v_i])$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5, M = N << 1;

int n, m, tot;
int ver[M], edge[M], nxt[M], head[N], outd[N];
double f[N];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
    outd[x]++;
}

double dp(int x) {
    if (f[x] >= 0) return f[x];
    f[x] = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        f[x] += (edge[i] + dp(y)) / outd[x];
    }
    return f[x];
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int x, y, z;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> z;
        add(x, y, z);
    }
    memset(f, -1, sizeof(f));
    cout << fixed << setprecision(2);
    cout << dp(1) << "\n";
    return 0;
}

218. 扑克牌

题意：在 54 张扑克牌里翻牌，求得到 A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开牌的期望是多少，小王大王可以当作某种花色。

  与上题类似，状态 f[a][b][c][d][x][y] 表示 a 张黑桃、b 张红桃、c 张梅花、d 张方块，大小王 x y 数值 $0\sim3$ 分别表示 a b c d 四堆中，4 表示未翻出。

$$dp[i]=\sum_{j=1}^m(1+dp[j])\times p[j]=1+\sum_{j=1}^mdp[j]\times p[j]$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

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

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const double INF = 1e20;
const int N = 14;

int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y) {
    if (a > 13 || b > 13 || c > 13 || d > 13) return INF;
    auto &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    int as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);
    if (as >= A && bs >= B && cs >= C && ds >= D) return v = 0;
    int sum = as + bs + cs + ds;
    sum = 54 - sum;
    if (sum == 0) return INF;
    v = 1;
    v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
    v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
    v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
    v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
    if (x == 4) {
        double tmp = INF;
        for (int i = 0; i < 4; ++i)
            tmp = min(tmp, 1.0 / sum * dp(a, b, c, d, i, y));
        v += tmp;
    }
    if (y == 4) {
        double tmp = INF;
        for (int i = 0; i < 4; ++i)
            tmp = min(tmp, 1.0 / sum * dp(a, b, c, d, x, i));
        v += tmp;
    }
    return v;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof(f));
    double res = dp(0, 0, 0, 0, 4, 4);
    if (res > INF / 2) res = -1;
    cout << fixed << setprecision(3);
    cout << res << "\n";
    return 0;
}