RenaMoe's Blog

念念不忘，必有回响

0%

21年1月2日 省选五校联合集训考试二

发表于 更新于 分类于 Valine：

数论 + 二分图匹配 + ？。

A 完全平方数

题目

给出 \(n\)，求 \(a+b=n\) 且 \(ab\) 是完全平方数的 \((a,b)\) 方案数。

\(T\le 200\)，\(n\le 10^9\)。

数论。

设 \(a=gx,b=gy\)，其中 \(g=\gcd(a,b)\)，那么 \(\gcd(x,y)=1\)，\(n=g(x+y)\)，\(ab=g^2xy\)。

因为 \(g^2\) 是完全平方数，所以 \(x,y\) 也都必须是完全平方数，所以可以 \(\mathcal O(\sqrt{\frac{n}{g}})\) 枚举。

我们可以 \(\displaystyle \mathcal O\bigg(\sum_{g|n,}\sqrt{\frac{n}{g}}\bigg)\) 枚举来做了，是 70分。

那么让 \(\mu(g)\neq 0\)（即 \(g\) 没有平方项因子），且不限制 \(x,y\) 互质（可以理解为将 \(g\) 中的平方因子移到 \(x,y\) 中）。

最后复杂度 \(\displaystyle \mathcal O\bigg(\sum_{g|n,\mu(g)\neq 0}\sqrt{\frac{n}{g}}\bigg)\)，上界似乎是几十万。

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
57
58
59
60
61
62
const int N = 1e5 + 9;

int T, n, sqr, cntp, ans;
int pri[N];
bool np[N];
vector<int> fac;

inline void get_prime() {
    for (int i = 2; i < N; ++i) {
        if (!np[i]) pri[++cntp] = i;
        for (int j = 1; j <= cntp; ++j) {
            int k = i * pri[j];
            if (k >= N) break;
            np[k] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

inline bool is_sq(int x) {
    int t = sqrt(x);
    return t * t == x;
}

inline void calc(int lim) {
    for (int i = 1; i * i <= lim; ++i) {
        int j = lim - (i * i);
        if (j < i * i) break;
        if (!is_sq(j)) continue;
        ++ans;
    }
}

inline void main() {
    get_prime();
    cin >> T;
    while (T--) {
        cin >> n;
        if (n & 1) {
            cout << "0\n";
            continue;
        }
        n >>= 1;
        ans = 0, fac.clear();
        int t = n;
        for (int i = 1; i <= cntp; ++i) {
            if (t % pri[i]) continue;
            fac.push_back(pri[i]);
            while (t % pri[i] == 0) t /= pri[i];
        }
        if (t > 1) fac.push_back(t);

        int maxn = 1 << (int)fac.size();
        for (int s = 0; s < maxn; ++s) {
            int d = 1;
            for (int i = 0; i < (int)fac.size(); ++i)
                if (s & (1 << i)) d *= fac[i];
            calc(n / d);
        }
        cout << ans << "\n";
    }
}

B 素数

题目

有 \(n\) 张不同的卡片，每张有正整数\(a_i\)。进行 \(m\) 轮操作，每轮操作选 \(2\) 张卡片，要求卡片上的数之和是素数，并将这 \(2\) 张卡片标记。问 \(m\) 轮之后最多标记多少张卡片？

\(1\le n,m\le 3000\)，\(1\le a_i\le 10^6\)。

二分图匹配。

贪心地想，前几次选取没标记的一对卡片标记，剩余操作再每次标记一张。

观察匹配条件，发现 \(\ge 2\) 的素数都是奇数，只能是一个奇数和一个偶数。去掉 \(1\) 后，剩下的卡片就可以建成二分图。

再考虑 \(1\)：两个 \(1\) 可以匹配，也可以与其他偶数匹配。所以优先让其他数字跑二分图最大匹配，再把 \(1\) 当做奇数点加到图里再跑一遍（不清空）。

求出来所以贡献为 \(2\) 的点，剩下的满足要求的点贡献为 \(1\)。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
const int N = 5e5 + 9;
const int M = 4e6 + 9;
const int INF = 0x3f3f3f3f;

struct Graph {
    int cnt;
    int head[N], nxt[N], to[N], flow[N];
    Graph() : cnt(1) {}
    inline void add(int u, int v, int w) {
        nxt[++cnt] = head[u], to[cnt] = v, flow[cnt] = w, head[u] = cnt;
        nxt[++cnt] = head[v], to[cnt] = u, flow[cnt] = 0, head[v] = cnt;
    }
    inline void clear() {
        cnt = 1;
        memset(head, 0, sizeof head);
    }
} G;

int n, m, tot, cntp, cnt1, one, S, T;
int a[N], pri[M];
bool np[M], can[N];

inline void get_prime() {
    const int maxn = 2e6;
    np[1] = true;
    for (int i = 2; i <= maxn; ++i) {
        if (!np[i]) pri[++cntp] = i;
        for (int j = 1; j <= cntp && i * pri[j] <= maxn; ++j) {
            np[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

namespace MaxFlow {
    int cur[N], deep[N];
    bool inq[N];
    queue<int> q;
    inline bool bfs() {
        for (int i = 1; i <= tot; ++i)
            cur[i] = G.head[i], deep[i] = INF, inq[i] = false;
        q.push(S), deep[S] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), inq[u] = false;
            for (int i = G.head[u]; i; i = G.nxt[i]) {
                int v = G.to[i];
                if (G.flow[i] && deep[v] > deep[u] + 1) {
                    deep[v] = deep[u] + 1;
                    if (!inq[v]) q.push(v), inq[v] = true;
                }
            }
        }
        return deep[T] != INF;
    }
    int dfs(int u, int lim) {
        if (u == T || !lim) return lim;
        int rest = lim;
        for (int &i = cur[u]; i; i = G.nxt[i]) {
            int v = G.to[i];
            if (deep[v] != deep[u] + 1 || !G.flow[i]) continue;
            int t = dfs(v, min(rest, G.flow[i]));
            if (!t) deep[v] = INF;
            G.flow[i] -= t, G.flow[i ^ 1] += t, rest -= t;
            if (!rest) break;
        }
        return lim - rest;
    }
    inline int Dinic() {
        int maxflow = 0, t;
        while (bfs()) {
            while ((t = dfs(S, INF))) maxflow += t;
        }
        return maxflow;
    }
}
using MaxFlow::Dinic;

inline void clear() {
    tot = cnt1 = 0;
    memset(can, 0, sizeof can);
    G.clear();
}

inline void main() {
    get_prime();
    while (cin >> n >> m) {
        clear();
        for (int i = 1; i <= n; ++i) cin >> a[i];
        tot = n, S = ++tot, T = ++tot, one = ++tot;
        for (int i = 1; i <= n; ++i) {
            if (a[i] == 1) {
                ++cnt1;
                continue;
            }
            if (a[i] & 1) {
                G.add(S, i, 1);
                for (int j = 1; j <= n; ++j) {
                    if (a[j] & 1) continue;
                    if (np[a[i] + a[j]]) continue;
                    G.add(i, j, 1);
                    can[i] = can[j] = true;
                }
            }
            else G.add(i, T, 1);
        }
        int mf = Dinic();
        if (cnt1) {
            can[one] |= cnt1 > 1;
            G.add(S, one, cnt1);
            for (int i = 1; i <= n; ++i) {
                if (a[i] == 1 || np[a[i] + 1]) continue;
                G.add(one, i, 1);
                can[one] = can[i] = true;
            }
            int t = Dinic(), c1 = cnt1;
            mf += t, c1 -= t;
            mf += c1 / 2;
        }
        // 最后这里细节很多
        int ans = 0, sum = 0;
        for (int i = 1; i <= n; ++i) sum += can[i];
        sum += cnt1 * can[one];
        if (mf >= m) ans = m * 2;
        else if (mf * 2 >= sum) ans = sum;
        else {
            ans = min(sum, m + mf);
        }
        cout << ans << '\n';
    }
}

C 广播

题目