题意

给你一个长度<=$1e5$的数组,每次可以进行的操作为
1.[l,r]区间内所有数乘上一个w(w<=100)
2.求[l,r]区间内的所有数的欧拉函数和

分析

以为每次w都<=100,有可能乘之后的结果大于1e9这样子用phi会爆炸空间
所以就得想怎么直接更新tr[u].sum,赛场上队友给的思路其实就是题解思路
那时候没认真想 考虑将w分解质因数p1,p2,p3....pk.
因为w<=100,100以内质数的个数是<=30个的,我们用bitset做一个状态压缩qwq

pushup

bitset可以看作是一个编码,若第i位为1,表示primes[i]在这个区间里所有
数都有这个质因数
然后区间合并的时候就可以把左右区间的bitset做一个&运算表示两个区间共有的质因子
编码,这样就很方便

modify

最最最难的modify操作来了唔
将w分解为{pi,cnti},pi表示有的质因子,cnti表示这个pi质因子在区间中出现的次数
情况

a.tr[u].l>=l&&tr[u].r<=r&&tr[u].tg[d.x]

其中tr[u].tg[d.x]表示当前这个节点表示的区间内的所有数都有primes[d.x]这个因子

那么直接更新tr[u].flag,tr[u].sum就好

更新为:

    tr[u].flag=tr[u].flag * qmi(primes[d.x],d.y)%mod;
    tr[u].sum=tr[u].sum* qmi(primes[d.x],d.y)%mod;

b.tr[u].l==tr[u].r

此时是暴力修改

1)若tr[u].tg[d.x]=1 和上面一样

2)若tr[u].tg[d.x]=0 多乘一个(1-1/primes[d.x])

                tr[u].tg[d.x]=1;
                tr[u].sum=tr[u].sum*(primes[d.x]-1)%mod;
                tr[u].sum=tr[u].sum*qmi(primes[d.x],d.y-1)%mod;

c.否则就继续递归啦

这么乱搞欧拉函数只要搞前100个数就行了
代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define x first
#define y second
const int N=1e5+10,M=110,mod=998244353;
int euler[M],primes[M],cnt;
bool vis[M];
int c[M][30];
bitset<30>st[M];
ll qmi(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b%2) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void getEuler()
{
    euler[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!vis[i])
        {
            primes[cnt++]=i;
            euler[i]=i-1;
        }
        //每个数只会被它的最小质因数筛选掉
        // 2 
        for(int j=0;primes[j]*i<M;j++)
        {
            vis[primes[j]*i]=true;//primes[j]*i的最小质因数是primes[j]
            if(i%primes[j]==0)  
            {
                euler[i*primes[j]]=euler[i]*primes[j];
                break;
            }
            euler[i*primes[j]]=euler[i]*(primes[j]-1);
        }
    }
}
ll w[N];
struct node
{

    int l,r;
    ll sum;
    ll flag;
    bitset<30>tg;//tg是一个由30个位组成的对象,用bitset函数可以方便地
    //访问其中的任意一位,bitset中的位从0开始编号,0是最右边的位
}tr[N<<2];
void pushup(int u)
{
    node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    root.sum=left.sum+right.sum;
    root.tg=left.tg&right.tg;//两个bitset对象进行按与运算
}
void build(int u,int l,int r)
{
    if(l==r)    
    {
        tr[u]={l,r,euler[w[l]],1,st[w[r]]};//st[w[r]]->表示所以一个30位的编码,从从右边开始第i位为1
        //表示primes[i-1]这个质因子在区间中出现过
        return;
    }
    tr[u]={l,r,0,1};
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u)
{
    node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    left.flag=left.flag*root.flag%mod;
    right.flag=right.flag*root.flag%mod;
    left.sum=left.sum*root.flag%mod;
    right.sum=right.sum*root.flag%mod;
    root.flag=1;
}
void modify(int u,int l,int r,pii d)
{
        if(tr[u].l>=l&&tr[u].r<=r&&tr[u].tg[d.x])
        {
            tr[u].flag=tr[u].flag*qmi(primes[d.x],d.y)%mod;
            tr[u].sum=tr[u].sum*qmi(primes[d.x],d.y)%mod;
        }
        else if(tr[u].l==tr[u].r)
        {
            if(tr[u].tg[d.x]) 
                tr[u].sum=tr[u].sum*qmi(primes[d.x],d.y)%mod;
            else
            {
                tr[u].tg[d.x]=1;
                tr[u].sum=tr[u].sum*(primes[d.x]-1)%mod;
                tr[u].sum=tr[u].sum*qmi(primes[d.x],d.y-1)%mod;
            }
        }
        else
        {
            if(tr[u].flag>1)    pushdown(u);
            int mid=tr[u].l+tr[u].r>>1;
            if(l<=mid)  modify(u<<1,l,r,d);
            if(r>mid)   modify(u<<1|1,l,r,d);
            pushup(u);
        }
}
ll query(int u,int l,int r)
{
        if(tr[u].l>=l&&tr[u].r<=r)  return tr[u].sum;
        if(tr[u].flag>1)  pushdown(u);
        ll res=0;           
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) res=query(u<<1,l,r);
        if(r>mid)   res+=query(u<<1|1,l,r);
        res%=mod;
        return res;
}
int main()
{
    getEuler();
    for(int i=1;i<M;i++)
    {
        for(int j=0;j<cnt;j++)
        {
            int x=i;
            while(x%primes[j]==0)   c[i][j]++,x/=primes[j];
            st[i][j]=c[i][j];
        }
    }
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%lld",&w[i]);
    build(1,1,n);
    int opt,l,r,d;
    vector<ll>ans;
    while(m--)
    {
        scanf("%d%d%d",&opt,&l,&r);
        if(opt) ans.push_back(query(1,l,r));
        else
        {
            scanf("%lld",&d);
            for(int i=0;i<cnt;i++)
                    if(c[d][i])   modify(1,l,r,(pii){i,c[d][i]});

        }
    }
    for(int i=0;i<ans.size()-1;i++)   printf("%lld\n",ans[i]);
    if(ans.size()) printf("%lld",ans.back());
    return 0;
}