题解：P13679 [IAMOI R2] 传奇模数

· · 题解

题目大意：

求式子 \left(\lfloor\dfrac{1}{998244353}\rfloor+\lfloor\dfrac{2}{998244353}\rfloor+\dots+\lfloor\dfrac{n}{998244353}\rfloor\right)\bmod 998244353 的值。

思路一：

直接暴力。
扫 1 到 n 所有整数，将它们除以 998244353 的值累加，最后对 998244353 取余即可。
代码就不展示了。
看看和蔼可亲的数据范围，能过就怪了。

思路二：

既然一位一位枚举不行，我们就 998244353 位 998244353 位的枚举。
我们发现，每过 998244353 位除得的答案增加 1。
我们可以定义一个变量 j，记录当前每次除得的答案。
同时，它也是之前进行过的轮数。
首先，我们一轮一轮枚举答案，最后，将凑不成一轮的单独统计就大功告成啦！

代码：

#include<bits/stdc++.h>
using namespace std;
constexpr long long N=998244353;
long long n,ans; 
int main() {
    cin>>n;
    int j=0;
    for(int i=0;i+N<=n;i+=N){   //虽然题目没写，但0也要算进去
        ans+=j*N;
        ans%=N;
        j++;
    }
    ans+=(n-N*j+1)*j;  //同理，记得算0
    ans%=N;
    cout<<ans;
    return 0;
}

这样我们就成功拿到了20分。

思路三：

进一步优化思路二的代码，我们发现：

ans+=j*N;
ans%=N;

由于 j \times N 是 N 的倍数，这两个语句执行完后 ans 的值不会改变。
所以，我们根本不需要循环，只要处理凑不成一轮的就行！

代码：

#include<bits/stdc++.h>
using namespace std;
constexpr long long N=998244353;
long long n,ans; 
int main() {
    cin>>n;
    ans+=(n%N+1)*(n/N);
    ans%=N;
    cout<<ans;
    return 0;
}

大家还是要自己写写，虽然核心代码只有 4 行，但想要一步步推出来对初学者来说还是不容易的。