传奇模数 题解

· · 题解

其实官方题解已经讲得很好了，自己就是补充一下，顺便说一下自己赛时思路。

1.题意

同官方题解，在这里我们定义 p=998244353。

对于正整数 n，求 \left(\lfloor\dfrac{1}{p}\rfloor+\lfloor\dfrac{2}{p}\rfloor+\dots+\lfloor\dfrac{n}{p}\rfloor\right)\bmod p。

2.我会暴力

枚举 p 从 1 到 n，算 \sum\limits_{i=1}^{n} \lfloor \frac{i}{p} \rfloor（假如看不懂求和符号西格玛请出门右转看数学百科西格玛稍稍了解一下如何运算即可）。当然也可以稍稍优化一下，从 p 开始。但是很可惜，考场上我想不出这个。

只得赛后打个代码给各位献丑：

#include <bits/stdc++.h>
#define int long long
using namespace std ;
int n , ans ;
const int p = 998244353 ;
signed main () {
  cin >> n ;
  for (int i = p ; i <= n ; i ++) {
    ans += i / p ;
    ans %= p ;
  }
  cout << ans % p ;
}

竟然优化后有 40 pts！

3.转向规律

既然暴力不行，那就找找规律。

我们注意到：

所以，不必要一一枚举，只需每次加上 p 就行了，或者枚举到 \frac{n}{p}，只要最后再末尾判断一次就行了。

赛时代码加了些注释，由于太紧张，码风不太好，见谅：

#include <bits/stdc++.h>
using namespace std ;
#define int long long
const int mod = 998244353 ;
int n , ans ;
signed main () {
    ios::sync_with_stdio (false) ;
    cin.tie (NULL) ; cout.tie (NULL) ;
    cin >> n ;
    int x = n / 998244353 ;
    int y = n % 998244353 ;
    for (int i = 0 ; i < x ; i ++) {  // 枚举到 <x，最后尾判。
        ans += i * 998244353 ; //从 kp 到 (k+1)p 共有 p（在这里是 mod） 个。
        ans %= mod ;
    }
    ans += (y + 1) * x ; //尾判，显然最后有 y+1 个 k=x。  
    cout << ans % mod ;
    return 0 ;
}

上交一测，结果：

怎么回事？

4.数学优化

令 x=\frac{n}{p}，下面代码：

for (int i = 0 ; i < x ; i ++) {  
    ans += i * p ; 
    ans %= mod ;
}

不难看出：ans=\sum\limits_{i=0}^{x-1} i\times p，再进行一些一些操作：

\begin{aligned} ans&=\sum\limits_{i=0}^{x-1} i\times p \\ &=0+p+2p+3p+\dots+(x-1)p \\ &=\left[1+2+\dots+\left(x-1\right)\right]p \\ \end{aligned}

根据小学二年级就学过的等差数列求和公式 S=\frac{(a_1+a_n)n}{2}（n 为数列的个数），可知：ans=\frac{(1+x-1)(x-1)}{2}\times p=\frac{x(x-1)\times p}{2}，这样复杂度就降为 \mathcal{O}(1) 了，十分优秀，妈妈再也不会担心我过不了了！

放上赛时稍加修改的代码：

#include <bits/stdc++.h>
using namespace std ;
#define int long long
const int p = 998244353 ;
int n , ans ;
signed main () {
    ios::sync_with_stdio (false) ;
    cin.tie (NULL) ; cout.tie (NULL) ;
    cin >> n ;
    int x = n / 998244353 ;
    int y = n % 998244353 ;
    ans += x % p * (x - 1) % p * p % p / 2 % p ;
    /*1+x+..+(x-1)=(1+x-1)*(x-1)/2*/
    ans += (y + 1) * x ;
    cout << ans % p ;
    return 0 ;
}