自动搬运

查看原文

来自洛谷，原作者为

	Vingying **

搬运于2025-08-24 21:58:14，当前版本为作者最后更新于2018-03-03 20:04:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

卡常大赛...... 最后没开O2比开了O2还快？！

首先看题，求区间gcd和lcm，我们可以将这个区间内的每个数分解质因数，gcd的话对每个质数个数取min，lcm的话取max，然而直接线段树上每个节点存该质数出现多少次的话铁定MLE。

这题的数据范围很神奇：每个值在[1,100]以内，而且题目只让求gcd和lcm（S操作可以通过求gcd求得），所以这就启发我们：将质数压起来。

我们发现：2^6=64, 2^7=128>100，所以一个区间内2的个数不超过6，而6可以用三个二进制位表示（6=4+2+0，即110）；同理，3^4=81, 3^5>100，所以一个区间内3的个数不超过4，也用三个二进制位表示（4=4+0+0，即100）；这样以此类推，可以得到一个区间内所有质数及其个数可以用31个二进制位表示。

而这31个二进制位，正好对应一个int的范围。所以每个节点存两个int：lcm和gcd，表示当前区间取gcd时的质数及其个数，取lcm时的质数及其个数。

然后就是普通的区间修改、区间查询了。不过还是有一些细节要注意。

...而且我被我一开始的大常数吓着了QAQ

下面是代码（这道题目前最长代码QAQ）

#include <stdio.h>
#include <string.h>
#include <cctype>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
    e=0;int ck=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ck=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
    e*=ck;
}
inline int max(int a,int b){if(a>b)return a;else return b;}
inline int min(int a,int b){if(a>b)return b;else return a;}
const int N=300050;int p;
inline int mi(int a,int b){ //快速幂 
    int ret=1;
    while(b){
        if(b&1)ret=(ret*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ret;
}
int n,Q,a[N],b[25],c1[25],c2[25],cnt[25];
//cnt,c1,c2都是用于保存当前值分解质因数后每个质数出现次数，
//不同地方用的数组不同 
//a数组为原数组，b数组含义见main函数 
int pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//素数打表 

#define ls id<<1
#define rs id<<1|1
inline int cal(int tmp){ //对当前数分解质因数 
    int i=0;memset(cnt,0,sizeof cnt);
    while(tmp>1){
        if(tmp%pri[i]==0){
            tmp/=pri[i];
            cnt[i]++;
            continue;
        }
        i++;
    }
    int v=0;
    for(register int i=0;i<=24;++i)v|=(cnt[i]<<b[i]);
    return v;
}

/*线段树开始*/ 
struct seg{
    int l,r;
    int gcd,lcm,lazy;
}t[N<<2];
inline int callcm(int v1,int v2){ //对v1和v2求lcm 
    int ret=0,p1,p2;memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);memset(cnt,0,sizeof cnt);
    c1[0]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;
    c1[1]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;
    c1[2]+=(1&v1)+(2&v1);v1>>=2;
    c1[3]+=(1&v1)+(2&v1);v1>>=2;
    for(register int i=p1=4;i<=24;++i,++p1){c1[i]+=(v1&1);v1>>=1;if(!v1)break;}if(p1==25)--p1;
    c2[0]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;
    c2[1]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;
    c2[2]+=(1&v2)+(2&v2);v2>>=2;
    c2[3]+=(1&v2)+(2&v2);v2>>=2;
    for(register int i=p2=4;i<=24;++i,++p2){c2[i]+=(v2&1);v2>>=1;if(!v2)break;}if(p2==25)--p2;
    int mx=max(p1,p2);
    for(register int i=0;i<=mx;++i)cnt[i]=max(c1[i],c2[i]);
    for(register int i=0;i<=mx;++i)ret|=(cnt[i]<<b[i]);
    return ret;
}
inline int calgcd(int v1,int v2){ //对v1和v2求gcd 
    int ret=0,p1,p2;memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);memset(cnt,0,sizeof cnt);
    c1[0]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;//质数2占的位 
    c1[1]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;//质数3占的位 
    c1[2]+=(1&v1)+(2&v1);v1>>=2;//质数5占的位 
    c1[3]+=(1&v1)+(2&v1);v1>>=2;//质数7占的位 
    for(register int i=p1=4;i<=24;++i,++p1){c1[i]+=(v1&1);v1>>=1;if(!v1)break;}if(p1==25)--p1;
    c2[0]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;//质数2占的位 
    c2[1]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;//质数3占的位 
    c2[2]+=(1&v2)+(2&v2);v2>>=2;//质数5占的位 
    c2[3]+=(1&v2)+(2&v2);v2>>=2;//质数7占的位 
    for(register int i=p2=4;i<=24;++i,++p2){c2[i]+=(v2&1);v2>>=1;if(!v2)break;}if(p2==25)--p2;
    int mn=min(p1,p2);
    for(register int i=0;i<=mn;++i)cnt[i]=min(c1[i],c2[i]);
    for(register int i=0;i<=mn;++i)ret|=(cnt[i]<<b[i]);
    return ret;
}
inline void pushup(int id){
    t[id].gcd=calgcd(t[ls].gcd,t[rs].gcd);
    t[id].lcm=callcm(t[ls].lcm,t[rs].lcm);
}
inline void pushdown(int id){
    if(t[id].lazy){
        t[ls].lazy=t[rs].lazy=t[id].lazy;
        if(t[id].lazy==1)t[ls].gcd=t[ls].lcm=t[rs].gcd=t[rs].lcm=0;
		//若当前值为1，则gcd和lcm都为1，但线段树中的gcd和lcm中存的都是质数，
		//所以将值设为0 
        else t[ls].gcd=t[ls].lcm=t[rs].gcd=t[rs].lcm=cal(t[id].lazy);
        t[id].lazy=0;
    }
}
void build(int l,int r,int id){ //线段树建树 
    t[id].l=l,t[id].r=r;t[id].lazy=0;
    if(l==r){
        if(a[l]==1){t[id].gcd=t[id].lcm=0;return;}
        t[id].gcd=t[id].lcm=cal(a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);build(mid+1,r,rs);
    pushup(id);
}
void change(int L,int R,int v,int vv,int id){ //v为要改变的值，vv为v分解质因数后的值 
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R){
        t[id].lazy=v;
        if(v==1){t[id].gcd=t[id].lcm=0;return;}
        t[id].gcd=t[id].lcm=vv;
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)change(L,R,v,vv,ls);
    else if(L>mid)change(L,R,v,vv,rs);
    else{
        change(L,mid,v,vv,ls);
        change(mid+1,R,v,vv,rs);
    }
    pushup(id);
}
int qgcd(int L,int R,int id){ //查询gcd 
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].gcd;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return qgcd(L,R,ls);
    else if(L>mid)return qgcd(L,R,rs);
    else return calgcd(qgcd(L,mid,ls),qgcd(mid+1,R,rs));
}
int qlcm(int L,int R,int id){ //查询lcm 
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].lcm;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return qlcm(L,R,ls);
    else if(L>mid)return qlcm(L,R,rs);
    else return callcm(qlcm(L,mid,ls),qlcm(mid+1,R,rs));
}
/*线段树结束*/ 

int main(){
    b[0]=0,b[1]=3;b[2]=6,b[3]=8;int bit=10;
    for(register int i=4;i<=24;++i)b[i]=bit++; //计算当前质数在二进制位上的位置 
    read(n),read(Q);
    for(register int i=1;i<=n;++i)read(a[i]);
    build(1,n,1); //建树 
    
    while(Q--){
        char opt[2];int x,y;
        scanf("%s",opt);read(x),read(y),read(p);
        switch(opt[0]){
            case 'L':{
                int tmp=qlcm(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量 
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位 
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位 
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位 
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位 
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                if(pos==25)--pos;
                /*这一部分为神奇的常数优化，因为从第5个质数开始，一个区间内仅会出现1个，所以不需要快速幂计算*/ 
                ans*=mi(pri[0],cnt[0]);
                ans*=mi(pri[1],cnt[1]);
                ans*=mi(pri[2],cnt[2]);
                ans*=mi(pri[3],cnt[3]);
                ans%=p;
                for(register int i=4;i<=pos;++i){
                	if(cnt[i])ans*=pri[i],ans%=p;
				}
				/*常数优化结束*/ 
                printf("%d\n",ans);
                break;
            }
            case 'G':{
                int tmp=qgcd(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量 
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位 
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位 
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位 
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位 
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                if(pos==25)--pos;
                /*这一部分为神奇的常数优化，因为从第5个质数开始，一个区间内仅会出现1个，所以不需要快速幂计算*/ 
                ans*=mi(pri[0],cnt[0]);
                ans*=mi(pri[1],cnt[1]);
                ans*=mi(pri[2],cnt[2]);
                ans*=mi(pri[3],cnt[3]);
                ans%=p;
                for(register int i=4;i<=pos;++i){
                	if(cnt[i])ans*=pri[i],ans%=p;
				}
				/*常数优化结束*/ 
                printf("%d\n",ans);
                break;
            }
            case 'C':{
            	int vv=cal(p);//先计算一步，优化时间 
                change(x,y,p,vv,1);
                break;
            }
            case 'S':{
                int tmp=qgcd(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量 
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位 
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位 
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位 
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位 
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                for(register int i=0;i<=pos;++i){
                    if(cnt[i])ans=ans%p*(cnt[i]+1)%p;
                    //计算答案，答案为每个质数出现次数+1之积 
                }
                printf("%d\n",ans%p);//因为写法问题，最后一定要mod p，否则p=1时GG 
                break;
            }
            default:{
                break;
            }
        }
    }
    return 0;
}