题目连接：http://www.spoj.com/problems/LGLOVE/
题意：给出n个初始序列a[1],a[2],...,a[n]，b[i]表示LCM(1,2,3,...,a[i])，即1~a[i]的最小公倍数
然后给出三种操作，注意：0<=i,j<n
0 i j p ：a[i]~a[j]都加上p
1 i j ：求LCM(b[i],b[i+1],...,b[j])
2 i j ：求GCD(b[i],b[i+1],...,b[j])
思路：
求LCM(b[i],b[i+1],...,b[j])，也就是求LCM(1,2,...a[i]),LCM(1,2,...a[i+1]),...,LCM(1,2,...a[j]),这些数的最小公倍数
如果细心的话可以发现，对于LCM(1,2,...,n1),LCM(1,2,...,n2)
假设n1<n2，那么LCM(1,2,...,n2)必定是LCM(1,2,...,n1)的倍数；反过来，LCM(1,2,...,n1)必定是LCM(1,2,...,n2)的约数。
因此针对操作1，其实就是求max(a[i],...,a[j])，设为maxval，然后求出LCM(1,2,...,maxval)即可。
针对操作2，其实就是求min(a[i],...,a[j])，设为minval，然后求出LCM(1,2,...,minval)即可。
到此，线段树方面的已经解决了，也就是只要存储该区间的最大值和最小值就行了。
接下来的话，就是如何预处理出LCM(1,2,...,n)了。
设z[n]=LCM(1,2,...,n)，那么我们可以用下面方式来预处理出所有值：
z[n]=LCM(z[n-1],n)
LCM(z[n-1],n)=(z[n-1]*n)/GCD(z[n-1],n)
而如果就按照这个公式这么做的话，由于最后是求模，首先要将除法的求模改成乘逆，即若a=b/c，那么a%mod=b*c^(m-2)%mod，
然后用到快速幂，再用辗转相除法。。。不用说，也知道，肯定会TLE！！！
再深入想想，n可以化为p1^a1 * p2^a2 * ... pk^ak，p1,p2,...，pk为n的质因数
从n的质因式分解中取出一个pi，剩下的设为m，注意m<n，那么n=m*pi
因为z[n-1]=LCM(1,2,...,n-1)，而m<=n-1，所以z[n-1]必定是m的倍数，设z[n-1]=a*m这样的话
即转化为 LCM(z[n-1],n)=LCM(z[n-1],m*pi)=z[n-1]*m*pi/GCD(z[n-1],m*pi)
而GCD(z[n-1],m*pi)=m*GCD(a,pi)
所以LCM(z[n-1],n)=z[n-1]*pi/GCD(a,pi)
1.若pi与a互质，即pi是这么一个数：在1~n-1中不存在pi这么个质因数，或者存在了，但是个数不够，还要乘一次
z[n]=z[n-1]*pi
2.若pi与a不互质，即z[n-1]中pi的个数与n中的个数相同，也就是说n中所有的因子都在z[n-1]中了，那么
z[n]=z[n-1]
对于每个质因数，设为p，那么p出现第一次，p^2出现第二次，p^3出现第三次...
那么我们只要在它第i次出现的时候，结果乘上它就行。
具体操作是和素数筛选法同时进行的，还是见代码吧。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R using namespace std;
const int INF=0x3f3f3f3f;
const int mod=;
const int maxn=;
long long z[maxn*]; //z[i]=LCM(1,2,...,i)
int n,m;
int maxval,minval;
/*
预处理z[i]
z[i]=LCM(1,2,3,...,i) 1<=i<=300000
*/
void init(){
memset(z,,sizeof(z));
z[]=; //0的话，最小公倍数为0
z[]=;
for(int i=;i<maxn*;i++){
if(z[i]==){
for(int j=*i;j<maxn*;j+=i)
z[j]=;
for(int j=i;j<maxn*;j*=i)
z[j]=i; //在i^m 的位置都先设为i，到时只要乘上就行
}
z[i]*=z[i-];
z[i]%mod;
}
} struct Node{
int maxv,minv; //存储区间的最大值，最小值
int add;
int lazy;
}tree[maxn<<]; void pushUp(int rt){
tree[rt].maxv=max(tree[rt<<].maxv,tree[rt<<|].maxv);
tree[rt].minv=min(tree[rt<<].minv,tree[rt<<|].minv);
}
void pushDown(int rt){
if(tree[rt].lazy){
tree[rt<<].add+=tree[rt].add;
tree[rt<<|].add+=tree[rt].add;
tree[rt<<].maxv+=tree[rt].add;
tree[rt<<].minv+=tree[rt].add; //一开始漏写了。。。
tree[rt<<|].maxv+=tree[rt].add; //一开始漏写了。。。
tree[rt<<|].minv+=tree[rt].add;
tree[rt<<].lazy=tree[rt<<|].lazy=true;
tree[rt].lazy=false;
tree[rt].add=;
}
}
void build(int rt,int L,int R){
tree[rt].lazy=false;
tree[rt].add=;
if(L==R){
int v;
scanf("%d",&v);
tree[rt].maxv=tree[rt].minv=v;
return;
}
int mid=(L+R)>>;
build(lson);
build(rson);
pushUp(rt);
} void update(int rt,int L,int R,int l,int r,int c){
if(l<=L&&R<=r){
tree[rt].maxv+=c;
tree[rt].minv+=c;
tree[rt].add+=c;
tree[rt].lazy=true;
return;
}
int mid=(L+R)>>;
pushDown(rt);
if(l<=mid)
update(lson,l,r,c);
if(r>mid)
update(rson,l,r,c);
pushUp(rt);
} void query(int rt,int L,int R,int l,int r,int op){
if(l<=L&&R<=r){
if(op==){
maxval=max(maxval,tree[rt].maxv);
}
else{
minval=min(minval,tree[rt].minv);
}
return;
}
pushDown(rt);
int mid=(L+R)>>;
if(l<=mid)
query(lson,l,r,op);
if(r>mid)
query(rson,l,r,op);
return;
}
int main()
{
init();
int op,a,b,p;
scanf("%d%d",&n,&m);
build(,,n);
for(int i=;i<=m;i++){
scanf("%d",&op);
if(op==){
scanf("%d%d%d",&a,&b,&p);
a++;
b++;
update(,,n,a,b,p);
}
else if(op==){
maxval=-INF;
scanf("%d%d",&a,&b);
a++;b++;
query(,,n,a,b,op);
if(maxval==)
printf("0\n");
else
printf("%lld\n",z[maxval]);
}
else{
minval=INF;
scanf("%d%d",&a,&b);
a++;b++;
query(,,n,a,b,op);
if(minval==)
printf("0\n");
else
printf("%lld\n",z[minval]);
}
}
return ;
}