牛客 - 智乃与无意义的题目

传送门：牛客 - 智乃与无意义的题目

思路分析

只需要维护区间积中素数因子的个数就行了
代码写的有点丑

样例输入

5 3
1 2 3 4 5
2 1 5
1 1 2
2 1 5

样例输出

16
20

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long
  
using namespace std;
  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  
const int INF = 0x3f3f3f3f;
const int mod=998244353;
const int N=1e5+5;
  
int a[N];
  
struct node {
    int l,r,mid,sum;
    vector<int>pr;
} tree[N<<2];
 
void pp(int x) {
    for(int i=0; i<8; i++) {
        if(tree[ls].pr[i]==0 || tree[rs].pr[i]==0) tree[x].pr[i]=max(tree[ls].pr[i],tree[rs].pr[i])%mod;
        else tree[x].pr[i]=(tree[ls].pr[i]+tree[rs].pr[i])%mod;
    }
}
  
void build(int x,int l,int r) {
    tree[x].l=l;
    for(int i=0; i<8; i++) tree[x].pr.push_back(0);
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    if(l==r) {
        int temp=a[l];
  
        while(temp%2==0) {
            tree[x].pr[2]++;
            temp/=2;
        }
        while(temp%3==0) {
            tree[x].pr[3]++;
            temp/=3;
        }
        while(temp%5==0) {
            tree[x].pr[5]++;
            temp/=5;
        }
        while(temp%7==0) {
            tree[x].pr[7]++;
            temp/=7;
        }
        if(temp>1) tree[x].pr[temp]++;
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}
  
  
void update(int x,int val,int pos) {
    if(tree[x].l==pos && tree[x].r==pos) {
        int temp=val;
        for(int i=0; i<8; i++) tree[x].pr[i]=0;
        while(temp%2==0) {
            tree[x].pr[2]++;
            temp/=2;
        }
        while(temp%3==0) {
            tree[x].pr[3]++;
            temp/=3;
        }
        while(temp%5==0) {
            tree[x].pr[5]++;
            temp/=5;
        }
        while(temp%7==0) {
            tree[x].pr[7]++;
            temp/=7;
        }
        if(temp>1) tree[x].pr[temp]++;
        return ;
    }
    int mid=tree[x].mid;
    if(pos<=mid) update(ls,val,pos);
    if(pos>mid) update(rs,val,pos);
    pp(x);
}
  
node query(int x,int l,int r) {
    if(l<=tree[x].l&&tree[x].r<=r)
        return tree[x];
    int mid=tree[x].mid;
    if(r<=mid) return query(ls,l,r);
    if(l>mid) return query(rs,l,r);
    else if(l<=mid && r>mid) {
        node lson=query(ls,l,r);
        node rson=query(rs,l,r);
        node ans;
        ans.sum=lson.sum*rson.sum%mod;
        vector<int>now;
        for(int i=0; i<8; i++) now.push_back(0);
        for(int i=0; i<8; i++) {
            if(lson.pr[i]==0 || rson.pr[i]==0) now[i]=max(lson.pr[i],rson.pr[i])%mod;
            else now[i]=(lson.pr[i]+rson.pr[i])%mod;
        }
        ans.pr=now;
        return ans;
    }
}
  
signed main() {
     
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
  
    int n,q;
    scanf("%lld%lld",&n,&q);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--) {
        int op;
        int l,r;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1) {
            update(1,r,l);
        } else {
            node now=query(1,l,r);
            ll ans=1;
            for(int i=0;i<8;i++) ans=(ans*(now.pr[i]+1))%mod;
            printf("%lld\n",ans);
  
        }
    }
  
  
  
  
    return 0;
}