这其实是个结论题,猜到结论后就不需要脑子了
首先直接报结论,2018以下的数字的平方对2018取余存在一个长度为6的循环节,这个结论得出我们可以直接暴力去验证,
重要的是我们怎么想到它,首先让我们回忆下扩展欧拉定理 ,当时成立,
然后我们考虑平方实际上是对指数*2,那么其实很快指数就会进入循环,那么我们大胆猜测所有数字的公共循环节不会太大,
打表发现正确后就可以做了
和正常代码不同的是,这是多组数据,要建立多次树,所以千万不能把区间的左端点和右端点保存在节点信息内,否则你
会死的很惨,此外,我们需要两个变量来记录这个位置的数是否已经处于循环节内。简单来说就是,有部分数字不是从第
一位开始循环的,比如2,它从第6位开始循环,是循环的第一个数字。
下面是代码
#include<bits/stdc++.h>
using namespace std;
#define ld u<<1
#define rd u<<1|1
const int N=5e4+100;
struct node
{
int sum[7],lazy,pos,cont;
}tr[N<<2];
void push_up(int u)
{
tr[u].cont=min(tr[ld].cont,tr[rd].cont);
tr[u].pos=0;
if(tr[u].cont>=5)for(int i=0;i<6;++i)tr[u].sum[i]=tr[ld].sum[(tr[ld].pos+i)%6]+tr[rd].sum[(tr[rd].pos+i)%6];
else
tr[u].sum[0]=tr[ld].sum[tr[ld].pos]+tr[rd].sum[tr[rd].pos];
}
void build(int u,int l,int r)
{
tr[u].lazy=tr[u].pos=tr[u].cont=0;
if(l==r)
{
cin >> tr[u].sum[0];
return;
}
int mid=l+r>>1;
build(ld,l,mid);
build(rd,mid+1,r);
push_up(u);
}
void push_down(int u)
{
if(tr[u].lazy)
{
tr[ld].lazy+=tr[u].lazy;
tr[rd].lazy+=tr[u].lazy;
tr[ld].pos=(tr[ld].pos+tr[u].lazy)%6;
tr[rd].pos=(tr[rd].pos+tr[u].lazy)%6;
tr[u].lazy=0;
}
}
void change(int u,int l,int r,int L,int R)
{
//cout << u << endl;
//cout << L << " " << R << endl;
if(L>=l&&R<=r&&tr[u].cont>=5)
{
tr[u].lazy++;
tr[u].pos++;
tr[u].pos%=6;
return;
}
if(L==R)
{
tr[u].cont++;
if(tr[u].cont<5)tr[u].sum[0]=(tr[u].sum[0]*tr[u].sum[0])%2018;
else if(tr[u].cont==5)
{
tr[u].sum[0]=(tr[u].sum[0]*tr[u].sum[0])%2018;
for(int i=1;i<6;++i)
tr[u].sum[i]=(tr[u].sum[i-1]*tr[u].sum[i-1])%2018;
}else tr[u].pos=(tr[u].pos+1)%6;
return;
}
push_down(u);
int mid=L+R>>1;
if(l<=mid)change(ld,l,r,L,mid);
if(r>mid)change(rd,l,r,mid+1,R);
push_up(u);
}
int query(int u,int l,int r,int L,int R)
{
if(L>=l&&R<=r)
return tr[u].sum[tr[u].pos];
int mid=L+R>>1;
int res=0;
push_down(u);
if(l<=mid)res+=query(ld,l,r,L,mid);
if(r>mid)res+=query(rd,l,r,mid+1,R);
return res;
}
int main()
{
int T;cin >> T;
int idx=0;
while(T--)
{
cout<<"Case #"<<(++idx)<<":\n";
int n,m;cin >> n;
build(1,1,n);
cin >> m;
while(m--)
{
string op;int l,r;
cin >> op >> l >> r;
if(op[0]=='Q')cout << query(1,l,r,1,n) << "\n";
else change(1,l,r,1,n);
}
}
}