记录编号	611719	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 pre] waht 先生的法阵	最终得分	100
用户昵称	梦那边的原神	是否通过	通过
代码语言	C++	运行时间	26.385 s
提交时间	2026-02-02 19:25:28	内存使用	45.83 MiB

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int N=2.5e5+10;
const int M=1005;
const int B=300; 
const int mod=998244353;
typedef long long ll;
int n,q,t,L[M],R[M],pos[N],vis[N],v[N],cnt,mn[N],f[N];
ll a[N],b[N],c[N],g[N],tag[M];
set<int>s[N];
int gcd(int n,int m){
	return m==0?n:gcd(m,n%m);
}
void init(int lim){
	for(int i=2;i<lim;i++){
		if(!vis[i])v[++cnt]=i,mn[i]=i;
		for(int j=1;j<=cnt&&v[j]*i<lim;j++){
			vis[i*v[j]]=1;
			mn[i*v[j]]=v[j];
			if(i%v[j]==0)break;
		}
	}
	return;
}
void work(int i,int val){
	while(val!=1){
		s[mn[val]].insert(i);
		val/=mn[val];
	}
	return;
}
void upd(int i){
	for(int j=R[i];j>=L[i];j--){
		if(j+c[j]>R[i]){
			f[j]=j+c[j],g[j]=a[j];
		}else{
			f[j]=f[j+c[j]];
			g[j]=(a[j]+g[j+c[j]])%mod;
		}
	}
	return;
}
void mul(int l,int r,int k){
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;i++){
			a[i]=(a[i]*k)%mod;
		}
		upd(pos[l]); 
	}else{
		mul(l,R[pos[l]],k);
		mul(L[pos[r]],r,k);
		for(int i=pos[l]+1;i<pos[r];i++){
			tag[i]=(tag[i]*k)%mod;
		}
	}
	return;
}
int stk[N],top,mk[M],st[M],tp;
void change(int l,int r,int k){
	auto itl=s[k].lower_bound(l);
	auto itr=s[k].lower_bound(r+1);
	for(auto it=itl;it!=itr;it++){
		int i=(*it);
		b[i]/=k,c[i]*=k;
		if(!mk[pos[i]]){
			st[++tp]=pos[i];
			mk[pos[i]]=1;
		}
		stk[++top]=i;
	}
	while(top){
		int i=stk[top--];
		if(b[i]%k)s[k].erase(i);
	}
	while(tp){
		int i=st[tp--];
		mk[i]=0,upd(i);
	}
	return;
}
ll query(int x){
	ll ans=0;
	while(1){
		ans=(ans+g[x]*tag[pos[x]]%mod)%mod;
		x=f[x];if(x>n)break;
	}
	return ans;
}
int main(){
	freopen("thupc_2025_pre_Mr.waht.in","r",stdin);
	freopen("thupc_2025_pre_Mr.waht.out","w",stdout);
	scanf("%d %d",&n,&q);t=n/B;init(N);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int i=1;i<=t;i++)L[i]=(i-1)*B+1,R[i]=i*B;
	if(R[t]<n){++t;L[t]=R[t-1]+1;R[t]=n;}
	for(int i=1;i<=t;i++){
		tag[i]=1;
		for(int j=L[i];j<=R[i];j++){
			c[j]=gcd(j,a[j]),b[j]=j/c[j];
			pos[j]=i,work(j,b[j]);
		}
		upd(i);
	}
	int o,x,y,z;
	while(q--){
		scanf("%d %d",&o,&x);
		if(o==1){
			scanf("%d %d",&y,&z);o=z;
			while(z!=1){
				change(x,y,mn[z]);
				z/=mn[z];
			}
			mul(x,y,o);
		}else printf("%lld\n",query(x));
	}
	return 0;
}