如何在A96802.前向走中拿时间空间双

开心就好

2026-07-07 16:17:31

发布于：北京

5阅读

0回复

0点赞

如何在：

A96802.前向走

中拿时间空间双修的成就

时空双修者

同时达成时间&空间双击败了99%的用户
很简单
ACGO_不愧是我

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> F(n + 1, 0);
    for (int y = 2; y <= n; ++y) F[y] = 1;
    int S = 1;
    int D = 0;
    int prev_dp = 1;
    for (int x = 2; x <= n; ++x) {
        int f = F[x];
        D += f;
        if (D >= m) D -= m;
        int dp_x = S + D;
        if (dp_x >= m) dp_x -= m;
        int delta = dp_x - prev_dp;
        if (delta < 0) delta += m;
        for (int y = x + x; y <= n; y += x) {
            F[y] += delta;
            if (F[y] >= m) F[y] -= m;
        }
        S += dp_x;
        if (S >= m) S -= m;
        prev_dp = dp_x;
    }
    cout << prev_dp << '\n';
    return 0;
}