首页 > ACM题库 > HDU-杭电 > HDU 3071-Gcd & Lcm game-线段树-[解题报告]HOJ
2014
03-01

HDU 3071-Gcd & Lcm game-线段树-[解题报告]HOJ

Gcd & Lcm game

问题描述 :

  Tired of playing too much computer games, alpc23 is planning to play a game on numbers. Because plus and subtraction is too easy for this gay, he wants to do some gcd and lcm operations in a number sequence. After playing it a few times, he has found it is also too boring. So he plan to do a more challenge job: he wants to change several numbers in this sequence and also work out the gcd or lcm of all the number in a subsequence of the whole sequence.
  To be a friend of this gay, you have been invented by him to play this interesting game with him. Of course, you need to work out the answers faster than him to get a free lunch, He he…

输入:

There are multiple test cases.
For each test case.The first line is the length of sequence n, and the number of queries q. (1<=n, q<=100000) The second line has n numbers, they are the initial n numbers of the sequence a1,a2, …,an,
From the third line to the q+2 line are the description of the q operations. They are the one of the two forms:
L k1 k2 p; you need to work out the value after mod p of lcm of the subsequence from k1 to k2, inclusive. (1<=k1<=k2<=n)
G k1 k2 p; you need to work out the value after mod p of gcd of the subsequence from k1 to k2, inclusive. (1<=k1<=k2<=n)
C k v; the k-th number of the sequence has been changed to v.
You can assume that all the numbers before and after the replacement are positive and no larger than 100.

输出:

There are multiple test cases.
For each test case.The first line is the length of sequence n, and the number of queries q. (1<=n, q<=100000) The second line has n numbers, they are the initial n numbers of the sequence a1,a2, …,an,
From the third line to the q+2 line are the description of the q operations. They are the one of the two forms:
L k1 k2 p; you need to work out the value after mod p of lcm of the subsequence from k1 to k2, inclusive. (1<=k1<=k2<=n)
G k1 k2 p; you need to work out the value after mod p of gcd of the subsequence from k1 to k2, inclusive. (1<=k1<=k2<=n)
C k v; the k-th number of the sequence has been changed to v.
You can assume that all the numbers before and after the replacement are positive and no larger than 100.

样例输入:

6 4
1 2 4 5 6 3
L 2 5 17
G 4 6 4
C 4 9
G 4 6 4

样例输出:

9
1
3

一道还不错的题目,解法:线段树+位压缩

对任意x<=100 其因子个数情况如下:

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  dpos[]={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};
//max num          7  4  2  2  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
//bit              3  3  2  2  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
//tot bit  3+3+2+2+21*1=31
// 0000 0000 0000 0000 0000 0000 0000 0000
//    |   |  | |                             
//    2   3  5 7 

所以,可以用一个32位的int数字表示x对应的各因子数

#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)>(y)?(x):(y))
inline int min(int x,int y){
    return _min(x&0x70000000,y&0x70000000)|_min(x&0x0e000000,y&0x0e000000)|_min(x&0x01800000,y&0x01800000)|_min(x&0x00600000,y&0x00600000)|((x&0x001fffff)&(y&0x001fffff));
}
inline int max(int x,int y){
    return _max(x&0x70000000,y&0x70000000)|_max(x&0x0e000000,y&0x0e000000)|_max(x&0x01800000,y&0x01800000)|_max(x&0x00600000,y&0x00600000)|((x&0x001fffff)|(y&0x001fffff));
}

自定义比较函数,即分别计算x与y的每个因子出现的最大与最小次数。

然后就是裸的单点更新,成段求最值的线段树了

#include<cstdio>

const int maxn=444444;
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  dpos[]={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 a[]={1,2,4,8,16,32,64};
int b[]={1,3,9,27,81};
int c[]={1,5,25};
int d[]={1,7,49};

#define lson l,mid,lrt
#define rson mid+1,r,rrt
#define mid ((l+r)>>1)
#define lrt rt<<1
#define rrt rt<<1|1

int MAX[maxn],MIN[maxn];
inline int turn(int x){
    int cnt,y=0;
    for(int i=0;i<25&&x>1;i++){
    for(cnt=0;x%prime[i]==0;x/=prime[i]) cnt++;
    y|=cnt<<dpos[i];
    }
    return y;
}
inline int back(int x,int p)
{
    long long y=1;
    int k=x>>dpos[0];y=y*a[k]%p;x^=k<<dpos[0];
    k=x>>dpos[1];y=y*b[k]%p;x^=k<<dpos[1];
    k=x>>dpos[2];y=y*c[k]%p;x^=k<<dpos[2];
    k=x>>dpos[3];y=y*d[k]%p;x^=k<<dpos[3];
    for(int i=4;i<25;i++)
    if(x&(1<<dpos[i])) y=y*prime[i]%p;
    return y;
}
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)>(y)?(x):(y))
inline int min(int x,int y){
    return _min(x&0x70000000,y&0x70000000)|_min(x&0x0e000000,y&0x0e000000)|_min(x&0x01800000,y&0x01800000)|_min(x&0x00600000,y&0x00600000)|((x&0x001fffff)&(y&0x001fffff));
}
inline int max(int x,int y){
    return _max(x&0x70000000,y&0x70000000)|_max(x&0x0e000000,y&0x0e000000)|_max(x&0x01800000,y&0x01800000)|_max(x&0x00600000,y&0x00600000)|((x&0x001fffff)|(y&0x001fffff));
}


inline void pushup(int rt){
    MAX[rt]=max(MAX[lrt],MAX[rrt]);
    MIN[rt]=min(MIN[lrt],MIN[rrt]);
}
void build(int l,int r,int rt){
    if(l==r){
    int x;scanf("%d",&x);
    MIN[rt]=MAX[rt]=turn(x);
    return;
    }
    build(lson);build(rson);
    pushup(rt);
}
void update(int k,int x,int l,int r,int rt){
    if(l==r){
    MAX[rt]=MIN[rt]=turn(x);
    return;
    }
    if(k<=mid) update(k,x,lson);
    else update(k,x,rson);
    pushup(rt);
}
int query_max(int s,int t,int l,int r,int rt){
    if(s<=l&&t>=r) return MAX[rt];
    int ret=0;
    if(s<=mid) ret=max(ret,query_max(s,t,lson));
    if(t>mid)  ret=max(ret,query_max(s,t,rson));
    return ret;
}
int query_min(int s,int t,int l,int r,int rt){
    if(s<=l&&t>=r) return MIN[rt];
    int ret=0x7fffffff;
    if(s<=mid) ret=min(ret,query_min(s,t,lson));
    if(t>mid)  ret=min(ret,query_min(s,t,rson));
    return ret;
}
int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
    build(1,n,1);
    char s[2];
    while(q--){
        scanf("%s",s);
        if(s[0]=='C'){
        int k,v;
        scanf("%d%d",&k,&v);
        update(k,v,1,n,1);
        }
        else if(s[0]=='L'){
        int k1,k2,p;
        scanf("%d%d%d",&k1,&k2,&p);
        int x=query_max(k1,k2,1,n,1);
        printf("%u\n",back(x,p));
        }
        else{
        int k1,k2,p;
        scanf("%d%d%d",&k1,&k2,&p);
        int x=query_min(k1,k2,1,n,1);
        printf("%u\n",back(x,p));
        }
    }
    }
    return 0;
}

参考:http://blog.csdn.net/wxfwxf328/article/details/7479874


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. [email protected]