数论，数据结构混合题。
首先为了处理修改需要引入，欧拉函数的以下若干结论 ：
-
1.当m与n互质时有ϕ(m ∗ n)==ϕ( m ) ∗ ϕ( n )
-
2.当k是一个质数时， ϕ( k ) == k−1
-
3.w是一个质数，此时如果 gcd(w,xi)==w 则 ϕ(w ∗x_{i})==w * ϕ(x_{i})。（如果一个区间里的x_i都满足这一点，可以区间修改）
有了上述结论以后，我们就可以用区间线段树，维护区间乘法的方式，维护每一次修改。
当区间中所有的数满足结论，3，时直接区间修改，否则判断是否满足结论，1，也能进行区修改。
不过值得注意的是，对于第二种区间修改，比较麻烦需要分情况讨论。详细见代码。
由于题目对时间要求，较高，因此需要卡常，以及各种优化，我们可以发现同一个，k，其操作的方式是一样的，因此每次都进行指数次操作即可。
还有我们只需要处理出[1,100]，这个区间内的质数即可。
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=998244353;
const int N=1e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
vector<int>cnt;//预处理出1~100之间的质数
int phi(int x)
{
int res=x;
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
bool st[110];
void primes()
{
for(int i=2;i<=100;i++)
{
if(!st[i])cnt.push_back(i);
st[i]=true;
for(int j=0;j<cnt.size()&&i*cnt[j]<=100;j++)
{
st[i*cnt[j]]=true;
if(i%cnt[j]==0)break;
}
}
}
vector<int> get_primes(int x)
{
vector<int>res;
for(int i=2;i<=x/i;i++)
{
int s=0;
while(x%i==0)x/=i,s++;
if(s)res.push_back(i);
}
if(x>1)res.push_back(x);
return res;
}//将乘数w进行，分解质因数，利用 gcd(m,n)=1则 phi(m*n)=phi(m)*phi(n)
int x[N];
struct node{
int l,r,val,add;
vector<int>p,lazy_p;
node():p(110,0),lazy_p(110,0){}
void init(int a,int b,int c,int d)
{
node();
l=a,r=b,val=c,add=d;
}
}tr[N*4];
void pushup(int u)
{
tr[u].val=(1ll*tr[u<<1].val+tr[u<<1|1].val)%mod;
for(auto c:cnt)tr[u].p[c]=tr[u<<1].p[c]+tr[u<<1|1].p[c];
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u].init(l,r,phi(x[l]),1);
vector<int>res=get_primes(x[l]);
for(auto c:res)tr[u].p[c]++;
}
else
{
tr[u].init(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)
{
auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
left.add=(1ll*root.add*left.add)%mod,left.val=(1ll*left.val*root.add)%mod;
right.add=(1ll*root.add*right.add)%mod,right.val=(1ll*right.val*root.add)%mod;
root.add=1;
for(auto i:cnt)
if(root.lazy_p[i])
{
left.p[i]=(left.r-left.l+1),left.lazy_p[i]=1;
right.p[i]=(right.r-right.l+1),right.lazy_p[i]=1;
root.lazy_p[i]=0;
}
}
void update(int u,int l,int r,int k,int mul)
{
// cout<<u<<' '<<l<<' '<<r<<endl;
if(tr[u].l>=l&&tr[u].r<=r&&tr[u].p[k]==tr[u].r-tr[u].l+1)
{
tr[u].add=(1ll*tr[u].add*qpow(k,mul))%mod;tr[u].val=(1ll*tr[u].val*qpow(k,mul))%mod;
// tr[u].p[k]+=tr[u].r-tr[u].l+1;tr[u].lazy_p[k]++;
}
else if(tr[u].l>=l&&tr[u].r<=r&&tr[u].p[k]==0)
{
tr[u].add=(1ll*tr[u].add*(k-1))%mod;tr[u].val=(1ll*tr[u].val*(k-1))%mod;
mul--;
if(mul)tr[u].add=(1ll*tr[u].add*qpow(k,mul))%mod,tr[u].val=(1ll*tr[u].val*qpow(k,mul))%mod;
tr[u].p[k]=tr[u].r-tr[u].l+1;tr[u].lazy_p[k]=1;
}
else
{
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
if(l<=mid)update(u<<1,l,r,k,mul);
if(r>mid)update(u<<1|1,l,r,k,mul);
pushup(u);
}
}
int query_sum(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].val;
else
{
pushdown(u);
int res=0;
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)res=query_sum(u<<1,l,r);
if(r>mid)res=(1ll*res+query_sum(u<<1|1,l,r))%mod;
return res;
}
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>x[i];
primes();
build(1,1,n);
while(m--)
{
int op;cin>>op;
int l,r;cin>>l>>r;
if(op)cout<<query_sum(1,l,r)<<endl;
else
{
int w;cin>>w;
// if(w==1)continue;
vector<int>res(110,0);
for(int i=2;i<=w/i;i++)
{
int s=0;
while(w%i==0)w/=i,s++;
res[i]=s;
}
if(w>1)res[w]=1;
for(auto c:cnt)
if(res[c])update(1,l,r,c,res[c]);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}
