P13679 [IAMOI R2] 传奇模数题解

P13679 [IAMOI R2] 传奇模数

分析

1. $n < M$：
   此时整体贡献值为 $0$。因为整体是向下取整，当 $n < M$ 的时候，每一个分数的值都是 $0$，没有任何贡献
2. $M \le n < 2M$：
   此时整体贡献值为 $(n - M + 1) \mod M$。在 $\sum_{i = M}^n \lfloor \frac{i}{M} \rfloor$ 中，每个 $i$ 的贡献值都为 $1$，所以 $[M,n]$ 的贡献值就是区间长度 $n - M + 1$。并且当 $n = 2M - 1$ 时，$n - M + 1 = M$，所以需要取模。
3. $2M \le n < 3M$： 此时整体贡献值为 $(n - 2M + 1) \times 2 \mod M$。首先，区间 $[0,2M)$ 的整体贡献值为 $0$。这个在上个区间的分析中提到过。所以我们只需要计算 $[2M, n]$ 的贡献值即可。$\sum_{i = 2M}^n \lfloor \frac{i}{M} \rfloor$ 中，每个 $i$ 的贡献值都为 $2$，所以 $[2M, n]$ 的贡献值就是 $(n - 2M + 1) \times 2$。当 $n = 3M - 1$ 时，$(n - 2M + 1) \times 2 = 2M$，所以也需要取模。

代码

#include <bits/stdc++.h>

using namespace std;
#define ll long long

ll n;
const int M = 998244353;

int main(){
    cin >> n;
    ll k = n / M;//区间长度
    cout << (k * (n - k * M + 1)) % M << endl;
    return 0;
}

AC记录