牛客练习赛82 B.Mocha 的序列(小思维 同余)

LINK

题意

对于每次询问333,需要回答∏i=lrai%(r−l+1)!\prod\limits_{i=l}^ra_i\%(r-l+1)!i=l∏r​ai​%(r−l+1)!

因为初始ai=ia_i=iai​=i

其中∏i=lrai\prod\limits_{i=l}^ra_ii=l∏r​ai​是连续的一段aia_iai​,区间长度为r−l+1r-l+1r−l+1

而注意到(r−l+1)!=1∗2∗3...∗(r−l+1)(r-l+1)!=1*2*3...*(r-l+1)(r−l+1)!=1∗2∗3...∗(r−l+1)

观察到初始时∏i=lrai=l∗(l+1)∗(l+2)..∗r\prod\limits_{i=l}^ra_i=l*(l+1)*(l+2)..*ri=l∏r​ai​=l∗(l+1)∗(l+2)..∗r

显然[l,r][l,r][l,r]中每个数模r−l+1r-l+1r−l+1互不同余,且一定有一个模r−l+1r-l+1r−l+1为零

扩展一下,对于i∈[1,r−l+1]i\in[1,r-l+1]i∈[1,r−l+1]每个数,在[l,r][l,r][l,r]中至少能找到一个数xxx使得iii是xxx的因子

那么显然∏i=lrai\prod\limits_{i=l}^ra_ii=l∏r​ai​有因子(r−l+1)!(r-l+1)!(r−l+1)!

所以不管序列怎么乘,怎么平方,答案都是000

#include <bits/stdc++.h>using namespace std;const int maxn = 1e6+10;int n,m;int main(){cin >> n >> m;for(int i=1;i<=m;i++){int type,l,r,k; cin >> type >> l >> r;if( type==3 )cout << 0 << endl;}}

如果觉得《牛客练习赛82 B.Mocha 的序列(小思维 同余)》对你有帮助，请点赞、收藏，并留下你的观点哦！