CCP-CSP 201912-5 魔数 暴力25

原题链接：CCP-CSP 201912-5 魔数

线段树是写不来的。。。

#include <bits/stdc++.h>
using namespace std;
#define ll  unsigned long long
const ll mod=2009731336725594113;
const int N=1e6+10;
ll U[5]={314882150829468584,427197303358170108,1022292690726729920,1698479428772363217,2006101093849356424};
ll a[N];

ll fun(ll x)
{
    return (x%mod)%2019;
}
ll mul(ll a,ll b)
{
    a%=mod;
    b%=mod;
    ll res=0;
    while(b)
    {
        if(b&1)
        {
            res+=a;
            if(res>=mod) res-=mod;
        }
        b>>=1;
        a<<=1;
        if(a>=mod) a-=mod;
    }
    return res;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,l,r;
    cin>>n>>q;
    for(int i=1;i<=n;i++) a[i]=i;
    while(q--)
    {
        cin>>l>>r;
        ll s=0;
        for(int i=l;i<=r;i++) s+=fun(a[i]);
        cout<<s<<endl;
        ll t=s%5;
        for(int i=l;i<=r;i++) a[i]=mul(a[i],U[t]);

    }
	return 0;
}