P13679 [IAMOI R2] 传奇模数题解

· · 题解

P13679 [IAMOI R2] 传奇模数

分析

令 M = 998244353。

  1. 此时整体贡献值为 $0$。因为整体是向下取整，当 $n < M$ 的时候，每一个分数的值都是 $0$，没有任何贡献
  2. 此时整体贡献值为 $(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. 此时整体贡献值为 $(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$，所以也需要取模。

以此类推，我们可以推到 kM \le n < (k + 1)M 的区间，其中 k 是一个非负整数。此时 [0,kM) 的贡献值为 0，[kM, n] 的贡献值为 (n - kM + 1) \times k \mod M。最后整体贡献值就为 (n - kM + 1) \times k \mod M。
最后注意 n \le 10^{18}，记得开 long long。

代码

所有的变量意义同上。

#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记录