记录编号	577565	评测结果	AAAAAWWAAA
题目名称	GCD和LCM问题	最终得分	80
用户昵称	op_组撒头屯	是否通过	未通过
代码语言	C++	运行时间	9.185 s
提交时间	2022-11-10 21:41:08	内存使用	139.22 MiB

#include <bits/stdc++.h>
using namespace std;
typedef unsigned ll;
const int N=50000+5;
const int T=550+5;
const ll inf=-1;
int n,q,t,len,mxv=50000;
int a[N],b[N];
int L[N],R[N],pos[N],tag[T]={0},g[N];
ll val[T],f[T][N];
bool ok[T][N]={0};
inline int gcd(int x,int y){
	if (y==0)return x;
	return gcd(y,x%y);
}
void stag(int l,int r){
	int posx=pos[l];
	for (int i=l;i<=r;i++){
		a[i]=tag[posx];
		g[i]=gcd(a[i],b[i]);
	}
	return ;
}
void getval(int l,int r){
	if (l>r)return ;
	int posx=pos[l];
	if (tag[posx])stag(l,r);
	for (int i=l;i<=r;i++){
		val[posx]=min(val[posx],(ll)(a[i]/g[i])*(b[i]/g[i]));
	}
	return ;
}
void update(int l,int r,int x){
	int posx=pos[l];ll now=inf;
	for (int i=l;i<=r;i++){
		a[i]=x;
		g[i]=gcd(x,b[i]);
		now=min(now,(ll)(x/g[i])*(b[i]/g[i]));
	}
	val[posx]=now;
	getval(L[posx],l-1);
	getval(r+1,R[posx]);
	tag[posx]=0;
	return ;
}
void change(int l,int r,int x){
	int posx=pos[l],posy=pos[r];
	if (posx==posy){
		update(l,r,x);
		return ;
	}
	update(l,R[posx],x);
	update(L[posy],r,x);
	for (int i=posx+1;i<=posy-1;i++){
		tag[i]=x;val[i]=f[i][x];
	}
	return ;
}
ll query(int l,int r){
	int posx=pos[l],posy=pos[r];
	if (posx==posy){
		if (tag[posx])stag(L[posx],R[posx]),tag[posx]=0;	
		ll ans=inf;
		for (int i=l;i<=r;i++)ans=min(ans,(ll)(a[i]/g[i])*(b[i]/g[i]));
		return ans;
	}
	ll ans=inf;
	if (tag[posx])stag(L[posx],R[posx]),tag[posx]=0;
	if (tag[posy])stag(L[posy],R[posy]),tag[posy]=0;
	for (int i=l;i<=R[posx];i++)ans=min(ans,(ll)(a[i]/g[i])*(b[i]/g[i]));
	for (int i=L[posy];i<=r;i++)ans=min(ans,(ll)(a[i]/g[i])*(b[i]/g[i]));
	for (int i=posx+1;i<=posy-1;i++)ans=min(ans,val[i]);
	return ans;
}
int main(){
	freopen ("gcdlcm.in","r",stdin);
	freopen ("gcdlcm.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)scanf("%d",&b[i]);
	if (n<=550)t=sqrt(n),len=n/t;
	else t=550,len=n/t;
	for (int i=1;i<=t;i++){
		L[i]=(i-1)*len+1;R[i]=i*len;
	}
	if (R[t]<n){
		t++;L[t]=R[t-1]+1;R[t]=n;
	}
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=t;i++){
		val[i]=inf;
		for (int j=L[i];j<=R[i];j++){
			pos[j]=i;
			ok[i][b[j]]=1;
			g[j]=gcd(a[j],b[j]);
			val[i]=min(val[i],(ll)(a[j]/g[j])*(b[j]/g[j]));
		}
		for (int j=1;j<=mxv;j++){
			for (int k=1;j*k<=mxv&&k<f[i][j];k++){
				if (ok[i][j*k]){
					f[i][j]=k;break;
				}
			}
			if (f[i][j]==inf)continue;
			for (int k=1;j*k<=mxv;k++){
				f[i][j*k]=min(f[i][j*k],f[i][j]*k);
			}
		}
	}
	while(q--){
		int opt,l,r,x;scanf("%d%d%d",&opt,&l,&r);
		if (opt==1){
			scanf("%d",&x);
			change(l,r,x);
		}
		else{
			printf("%u\n",query(l,r));
		}
	}
	return 0;
}