题解：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

，记录当前每次除得的答案。
同时，它也是之前进行过的轮数。
首先，我们一轮一轮枚举答案，最后，将凑不成一轮的单独统计就大功告成啦！

代码：

CPP

#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分。

思路三：

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

CPP

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

由于

j \times N

是

N

的倍数，这两个语句执行完后

ans

的值不会改变。
所以，我们根本不需要循环，只要处理凑不成一轮的就行！

代码：

CPP

#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

行，但想要一步步推出来对初学者来说还是不容易的。

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

文章操作

题目大意：

思路一：

思路二：

代码：

思路三：

代码：

相关推荐

评论

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