题解 | #A Simple Problem with Integers#

这其实是个结论题，猜到结论后就不需要脑子了

首先直接报结论，2018以下的数字的平方对2018取余存在一个长度为6的循环节，这个结论得出我们可以直接暴力去验证，

重要的是我们怎么想到它，首先让我们回忆下扩展欧拉定理 $a^b\mathrm{m}\mathrm{o}\mathrm{d}c=a^{b\mathrm{m}\mathrm{o}\mathrm{d}\phi (c)+\phi (c)}\mathrm{m}\mathrm{o}\mathrm{d}ca^\{b\}\; \backslash bmod\; c\; =\; a^\{b\; \backslash mod\; \backslash varphi(c)\; +\; \backslash varphi(c)\}\; \backslash bmod\; c$,当$b>=\phi (c)b>=\backslash varphi(c)$时成立，

然后我们考虑平方实际上是对指数*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);
        }

    }

}