提高组 CSP-S 2026 初赛模拟卷 10

#include <iostream>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p; // 保证 n 为正整数，p 为素数，cur 不会溢出 long long 类型
    int ans = 0;
    long long cur = p;
    while (cur <= n) {
        ans += n / cur;
        cur *= p;
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 100009;
int prime[N], tot, sd[N], sp[N];
bool vis[N];

void init() {
    sd[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            prime[++tot] = i;
            sd[i] = i + 1;
            sp[i] = i + 1;
        }
        for (int j = 1; j <= tot && i * prime[j] < N; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                sp[i * prime[j]] = sp[i] * prime[j] + 1;
                sd[i * prime[j]] = sd[i] / sp[i] * sp[i * prime[j]];
                break;
            } else {
                sp[i * prime[j]] = prime[j] + 1;
                sd[i * prime[j]] = sd[i] * sd[prime[j]];
            }
        }
    }
}

int main() {
    init();
    int n;
    cin >> n;
    cout << sd[n] << endl;
    return 0;
}

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

typedef long long ll;
ll T, a, m, ans;

ll quickpow(ll a, ll b) {
    if (b < 0) return 0;
    ll ret = 1;
    a %= m;
    while (b) {
        if (b & 1) ret = (ret * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return ret;
}

ll inverse(ll a, ll m) {
    return quickpow(a, m - 2);
}

int main() {
    cin >> a >> m;
    ans = inverse(a, m);
    cout << ans << " ";
    return 0;
}

（树上第二类欧拉序）将树视为一个图，每条边视为2条（对向的）有向边，通过DFS遍历形成一个环游，遵循以下规则：从根节点开始遍历，每次进入一个节点u时，立即将其记录到序列中；每次从u的某个子节点返回到u时，再次记录u。当节点u有多个子节点时，按照子节点编号从小到大的顺序依次访问。最终得到的欧拉序列总长度为2n-1（n为树的节点数），其中每个节点出现的次数等于其在树中的度数（根节点除外，由于初始进入会多记录一次，因此出现次数为度数加一）。

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

const int N = 1009;
vector<int> to[N];
int n, timer, euler[①];

void dfs(int u, int fa) {
    ++timer;
    ②;
    for (int i = 0; i < to[u].size(); ++i)
        if (to[u][i] != fa) dfs(to[u][i], u);
    ③;
}

int main() {
    cin >> n; // 保证输入的 1 <= u, v <= n <= 1000，且无环
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u)
        ④;
    dfs(1, 0);
    for (int i = 1; ⑤; ++i) cout << euler[i] << " ";
    cout << euler[2 * n - 1] << endl;
    return 0;
}

（中国邮路问题）邮递员需要从邮局出发，遍历他所负责的所有街道（每条街道至少经过一次），最后返回邮局。每条街道有不同的长度，请设计一条最短的路线。本质是在一个具有非负权的赋权连通图 G 中，找出一条总权最小的环游。这种环游称为最优环游。若 G 是欧拉图，则 G 的任意欧拉环游都是最优环游。若 G 不是欧拉图，则 G 的任意一个环游必定经过某些边不止一次，需要通过添加重复边来构造欧拉图，且保证添加的边总权最小。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dst(n + 1, vector<int>(n + 1, INT_MAX));
    vector<int> deg(n + 1, 0);
    ll total = 0;
    for (int i = 1; i <= n; ++i) dst[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if (①) {
            dst[u][v] = w;
            dst[v][u] = w;
        }
        deg[u]++;
        deg[v]++;
        total += w;
    }

    // Floyd-Warshall 算法：计算所有顶点对的最短路径
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (dst[i][k] == INT_MAX) continue;
            for (int j = 1; j <= n; ++j) {
                if (dst[k][j] == INT_MAX) continue;
                if (②)
                    dst[i][j] = dst[i][k] + dst[k][j];
            }
        }
    }

    vector<int> odd;
    for (int i = 1; i <= n; ++i)
        if (deg[i] % 2 == 1) odd.push_back(i);
    if (③) {
        cout << total << endl;
        return 0;
    }

    int k = odd.size();
    vector<long long> dp(1 << k, LLONG_MAX);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << k); ++mask) {
        if (dp[mask] == LLONG_MAX) continue;
        int i = 0;
        while (④) i++;
        if (i >= k) continue;
        for (int j = i + 1; j < k; ++j) {
            if (mask & (1 << j)) continue;
            if (dst[odd[i]][odd[j]] == INT_MAX) continue;
            int new_mask = ⑤;
            ll new_val = dp[mask] + dst[odd[i]][odd[j]];
            if (new_val < dp[new_mask]) dp[new_mask] = new_val;
        }
    }

    ll ans = total + dp[(1 << k) - 1];
    cout << ans << endl;
    return 0;
}