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

Cake_W · 2025-08-12 20:04:55 · 题解

分析

当我们输入的 n 小于 998244353 时，那么每个数除以 998244353 向下取整的结果一定等于 0。如果输入的 n 在 998244353 到 2\times998244353-1 时，那么这个区间内的每个数除以 998244353 向下取整的结果都为 1。同理，如果输入的 n 在 2\times998244353 到 3\times998244353-1 时，那么这个区间内的每个数除以 998244353 向下取整的结果都为 2。以此类推。

思路

不难发现，每个区间所有数除以 998244353 的结果的和模 998244353 一定等于 0，所以我们只需要算出最后一个非完整的区间有多少个数，再乘上 n 除以 998244353 向下取整的值就可以了。

代码

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