C++ 解法, 执行用时: 1110ms, 内存消耗: 177904K, 提交时间: 2022-03-29 20:38:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
const int maxm=1e7+10;
const ll mod=998244353;
ll sumv[maxn<<2],addv[maxn<<2],a[maxn],v,ans_sum,mind[maxm],val[maxm];
int ql,qr;

inline ll re(int x){
    if(x==1) return 0;
    return val[x];
}

inline void pushdown(int o,int L,int R){
    int M=(R+L)>>1;
    if(addv[o]){
        addv[o*2]+=addv[o];
        addv[o*2+1]+=addv[o];
        sumv[o*2]+=addv[o]*(M-L+1);
        sumv[o*2+1]+=addv[o]*(R-M);
        addv[o]=0;
    }
}

inline void pushup(int o){
    sumv[o]=sumv[o*2]+sumv[o*2+1];
}

void build(int o,int L,int R){
    int M=(L+R)>>1;
    if(L!=R){
        build(o*2,L,M);
        build(o*2+1,M+1,R);
        pushup(o);
    }
    else sumv[o]=a[L];
}

void add_tree(int o,int L,int R){
    if(ql<=L&&R<=qr){
        addv[o]+=v;
        sumv[o]+=1LL*(R-L+1)*v;
    }
    else{
        int M=(L+R)>>1;
        pushdown(o,L,R);
        if(ql<=M) add_tree(o*2,L,M);
        if(qr>M) add_tree(o*2+1,M+1,R);
        pushup(o);
    }
}

void query_tree(int o,int L,int R){
    if(ql<=L&&R<=qr){
        ans_sum+=sumv[o];
    }
    else{
        pushdown(o,L,R);
        int M=(L+R)>>1;
        if(ql<=M) query_tree(o*2,L,M);
        if(qr>M) query_tree(o*2+1,M+1,R);
        pushup(o);
    }
}

int main(){
	ios::sync_with_stdio(false);

	memset(mind,-1,sizeof(mind));
	mind[1] = 1;
    for(int i=2;i<maxm;i++) if(mind[i]==-1)
        for(int j=i;j<maxm;j+=i) if (mind[j]==-1)
            mind[j]=i;
    for(int i=2;i<maxm;i++) {
        int j=i/mind[i];
        val[i]=val[j]+mind[i];
    }
    //debug(val[15]);
	int n,q;scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);a[i]=re(a[i]);
    }
    build(1,1,n);
    while(q--){
        int op;scanf("%d%d%d",&op,&ql,&qr);
        if(op==1){
            ans_sum=0;
            query_tree(1,1,n);
            if(ans_sum==0) ans_sum=1;
            printf("%lld\n",ans_sum%mod);
        }
        else{
           int x;scanf("%d",&x);
            v=re(x);
            add_tree(1,1,n);
        }
    }
}