HDU 3071 Gcd & Lcm game

最新推荐文章于 2022-04-12 16:46:37 发布

Magic_insky

最新推荐文章于 2022-04-12 16:46:37 发布

阅读量1.4k

点赞数

分类专栏： HDU解题报告文章标签： HDU 线段树位压缩

本文链接：https://blog.csdn.net/insky_acm/article/details/10077963

版权

HDU解题报告专栏收录该内容

12 篇文章

订阅专栏

这是一篇关于如何使用位压缩技术处理线段树以解决HDU 3071题目的博客。文章指出，由于题目中涉及的前100个自然数的LCM过大，不能直接使用常规线段树。作者通过分析质因数，发现可以使用32位整数来表示质因子的数量，从而实现位压缩。博客详细介绍了位压缩的实现思路，并强调了在编写代码时需要注意的两点细节。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

纠结了很久的题目。看上去是一道裸的线段树，但是需要对数据做特殊的处理。

题意：n（1<=n<=10^5）个数字，q（1<=q<=10^5）个操作。每个操作可能有3种情况：1.询问[k1,k2]区间数字的GCD%p; 2.询问[k1,k2]区间数字的LCM%p; 3.将k位置的数字改为v。对于前两个操作输出对应的值。题目保证这n个数不管在什么时候都不超过100

对点修改，对区间查询，最基础的线段树。但是，前100个自然书的LCM非常大，超long long，不能直接套线段树。要用到位压缩。前100个数字里包含25个质数分别是：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。在一个数字里，质因子2最多出现6次（用3位2进制数表示），3最多出现4次（用3位2进制数表示），5最多出现2次（用2位2进制数表示），7最多出现2次，其余的最多出现1次（用1位2进制数表示）。全加起来3+3+2+2+21=31位，也就是说可以用一个32位整数表示质因子的数量。剩下的就是裸线段树了。

有2点需要注意的，写在代码注释里了。

#include<stdio.h>
#include<iostream>
using namespace std;

#define Maxn 100010

struct node
{
    int l,r,gcd,lcm;
}tree[Maxn*4];

int n,q,A[Maxn];
int prime[]={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};
int sp[]={28,25,23,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};

int change(int num);
void Count(int num,long long mod);
void Build(int cnt,int l,int r);
void update(int cnt,int s,int v);
int query(int cnt,int l,int r,char c);
int GCD(int a,int b);
int LCM(int a,int b);
int main()
{
    char c[2];
    long long p;
    int l,r,s,v,tmp;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&A[i]);
            A[i]=change(A[i]);
        }
        Build(1,1,n);
        while(q--)
        {
            scanf("%s",c);
            if(c[0]=='C')
            {
                scanf("%d%d",&s,&v);
                v=change(v);
                update(1,s,v);
            }
            else
            {
                scanf("%d%d%I64d",&l,&r,&p);
                tmp=query(1,l,r,c[0]);
                Count(tmp,p);
            }
        }
    }
    return 0;
}

int change(int num)
{
    int rt,tmp;
    rt=0;
    for(int i=0;i<25 && num>1;i++)
    {
        tmp=0;
        while(num%prime[i]==0)
        {
            num/=prime[i];
            tmp++;
        }
        rt=rt|(tmp<<sp[i]);
    }
    return rt;
}
void Count(int num,long long mod)
{
    long long ans;
    int tmp;
    ans=1%mod; //这里有个陷阱，如果num==0，mod==1，那么ans应该为0。
               //ans初始化为1的时候，最后的结果就为1，所以要初始化为1%mod
    for(int i=0;i<25;i++)
    {
        tmp=num>>sp[i];
        if(tmp==0)
            continue;
        for(int j=1;j<=tmp;j++)
            ans=(ans*prime[i])%mod;
        num=num^(tmp<<sp[i]);
    }
    printf("%I64d\n",ans);
}
void Build(int cnt,int l,int r)
{
    int mid=(l+r)/2;
    if(l==r)
    {
        tree[cnt].l=tree[cnt].r=l;
        tree[cnt].gcd=tree[cnt].lcm=A[l];
        return;
    }
    tree[cnt].l=l,tree[cnt].r=r;
    Build(2*cnt,l,mid);
    Build(2*cnt+1,mid+1,r);
    tree[cnt].gcd=GCD(tree[2*cnt].gcd,tree[2*cnt+1].gcd);
    tree[cnt].lcm=LCM(tree[2*cnt].lcm,tree[2*cnt+1].lcm);
}
void update(int cnt,int s,int v)
{
    int mid=(tree[cnt].l+tree[cnt].r)/2;
    if(tree[cnt].l==tree[cnt].r)
    {
        tree[cnt].gcd=tree[cnt].lcm=v;
        return;
    }
    if(s<=mid)
        update(cnt*2,s,v);
    else
        update(cnt*2+1,s,v);
    tree[cnt].gcd=GCD(tree[2*cnt].gcd,tree[2*cnt+1].gcd);
    tree[cnt].lcm=LCM(tree[2*cnt].lcm,tree[2*cnt+1].lcm);
}
int query(int cnt,int l,int r,char c)
{
    int mid=(tree[cnt].l+tree[cnt].r)/2;
    int rt;
    if(l<=tree[cnt].l && r>=tree[cnt].r)
    {
        if(c=='L')
            return tree[cnt].lcm;
        else
            return tree[cnt].gcd;
    }
    if(c=='L')
        rt=0;
    else
        rt=0x7fffffff;
    if(l<=mid)
    {
        if(c=='L')
            rt=LCM(rt,query(2*cnt,l,r,c));
        else
            rt=GCD(rt,query(2*cnt,l,r,c));
    }
    if(r>mid)
    {
        if(c=='L')
            rt=LCM(rt,query(2*cnt+1,l,r,c));
        else
            rt=GCD(rt,query(2*cnt+1,l,r,c));
    }
    return rt;
}

int GCD(int a,int b)
{
    return min(a&0x70000000,b&0x70000000)|min(a&0x0e000000,b&0x0e000000)|
           min(a&0x01800000,b&0x01800000)|min(a&0x00600000,b&0x00600000)|
           ((a&0x001fffff)&(b&0x001fffff));
}
int LCM(int a,int b)
{
    return max(a&0x70000000,b&0x70000000)|max(a&0x0e000000,b&0x0e000000)|
           max(a&0x01800000,b&0x01800000)|max(a&0x00600000,b&0x00600000)|
           ((a&0x001fffff)|(b&0x001fffff));
}
/*这么写会导致常数太大tle
int GCD(int a,int b)
{
    int tmp,tmpa,tmpb,rt;

    rt=0;
    for(int i=0;i<25;i++)
    {
        tmpa=a>>sp[i],tmpb=b>>sp[i];
        tmp=min(tmpa,tmpb);
        rt=rt|(tmp<<sp[i]);
        a=a^(tmpa<<sp[i]),b=b^(tmpb<<sp[i]);
    }
    return rt;
}
int LCM(int a,int b)
{
    int tmp,tmpa,tmpb,rt;

    rt=0;
    for(int i=0;i<25;i++)
    {
        tmpa=a>>sp[i],tmpb=b>>sp[i];
        tmp=max(tmpa,tmpb);
        rt=rt|(tmp<<sp[i]);
        a=a^(tmpa<<sp[i]),b=b^(tmpb<<sp[i]);
    }
    return rt;
}*/