HDU_3071 Gcd & Lcm game 【素数分解 + 线段树 + 状压】

一、题目

二、分析

　　非常好的一题。

　　首先考虑比较暴力的做法，肯定要按区间进行处理，对于$lcm$和$gcd$可以用标准的公式进行求，但是求$lcm$的时候是肯定会爆$long long$的。

　　考虑用素数分解，将所有的数分解后，发现素因子的个数有限，且每个因子的幂也有限，最多的也就是$2^_6$，然后可以考虑将素因子用二进制的每一位进行表示。对于$2,3,5,7$可能会要的多点，所以多给给几位就可以了，最后发现，刚好可以$32$位以内。

　　这里就需要写两个转换函数，然后利用$gcd$和$lcm$的性质进行求解和变换。最后考虑区间查询和单点修改，再用一个线段树即可。　　

三、AC代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <cmath>

using namespace std;

#define ll long long

#define Min(a,b) ((a)>(b)?(b):(a))

#define Max(a,b) ((a)>(b)?(a):(b))

#define lson (rt<<1)

#define rson (rt<<1|1)

const int MAXN = 1e5;

struct Node

{

    int L, G;

}segTree[MAXN<<2];

int Prime[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};

int Pos[25] = {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};

inline int Gcd(int x, int y)

{

    //最后是相&，如果继续用Min，相当于只用了一个导致WA

    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 Lcm(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质因素分解，并用二进制表示

inline int Turn(int x)

{

    int res, ans = 0;

    for(int i = 0; i < 25 && x > 1; i++) {

        res = 0;

        while(x%Prime[i] == 0) {

            res++;

            x/=Prime[i];

        }

        ans |= (res<<Pos[i]);

    }

    return ans;

}

int Mi2[] = {1, 2, 4, 8, 16, 32, 64};

int Mi3[] = {1, 3, 9, 27, 81};

int Mi5[] = {1, 5, 25};

int Mi7[] = {1, 7, 49};

//将二进制表示的数转转换成原来的数并取模

inline int Get(int x, int p)

{

    ll ans = 1;

    int res = x>>Pos[0];

    x ^= res<<Pos[0];   //消去表示2的位上的数

    ans = ans*Mi2[res]%p;

    //求3的指数并消去

    res = x>>Pos[1];    x ^= res<<Pos[1];   ans = ans * Mi3[res] % p;

    //求5的指数并消去

    res = x>>Pos[2];    x ^= res<<Pos[2];   ans = ans * Mi5[res] % p;

    //求7的指数并消去

    res = x>>Pos[3];    x ^= res<<Pos[3];   ans = ans * Mi7[res] % p;

    for(int i = 4; i < 25; i++) {

        if((x>>Pos[i])&1) {

            ans = ans * Prime[i] % p;

        }

    }

    return ans % p;

}

void Push_up(int rt)

{

    segTree[rt].G = Gcd(segTree[lson].G, segTree[rson].G);

    segTree[rt].L = Lcm(segTree[lson].L, segTree[rson].L);

    return;

}

void Build(int rt, int l, int r)

{

    if(l == r) {

        int a;

        scanf("%d", &a);

        segTree[rt].G = Turn(a);

        segTree[rt].L = Turn(a);

        return;

    }

    int mid = (l + r) >> 1;

    Build(lson, l, mid);

    Build(rson, mid + 1, r);

    Push_up(rt);

}

void Change(int rt, int l, int r, int pos, int val)

{

    if(l == r) {

        segTree[rt].G = Turn(val);

        segTree[rt].L = segTree[rt].G;

        return;

    }

    int mid = (l + r) >> 1;

    if(pos <= mid) {

        Change(lson, l, mid, pos, val);

    }

    else if (pos > mid) {

        Change(rson, mid + 1, r, pos, val);

    }

    Push_up(rt);

}

int anslcm, ansgcd;

void Query_lcm(int rt, int l, int r, int L, int R)

{

    if(L <= l && r <= R) {

        anslcm = Lcm(anslcm, segTree[rt].L);

        return;

    }

    int mid = (l + r) >> 1;

    if(L <= mid) {

        Query_lcm(lson, l, mid, L, R);

    }

    if(R > mid) {

        Query_lcm(rson, mid + 1, r, L, R);

    }

}

void Query_gcd(int rt, int l, int r, int L, int R)

{

    if(L <= l && r <= R) {

        ansgcd = Gcd(ansgcd, segTree[rt].G);

        return;

    }

    int mid = (l + r) >> 1;

    if(L <= mid) {

        Query_gcd(lson, l, mid, L, R);

    }

    if(R > mid) {

        Query_gcd(rson, mid + 1, r, L, R);

    }

}

int main()

{

    //freopen("input.txt", "r", stdin);

    int N, Q;

    while(scanf("%d%d", &N, &Q) != EOF) {

        Build(1, 1, N);

        char s[2];

        for(int i = 0; i < Q; i++) {

            scanf("%s", s);

            int a, b, c;

            if(s[0] == 'L') {

                anslcm = 0;

                scanf("%d%d%d", &a, &b, &c);

                Query_lcm(1, 1, N, a, b);

                int ans = Get(anslcm, c);

                printf("%d\n", ans);

            }

            else if(s[0] == 'G') {

                ansgcd = 0x7fffffff;

                scanf("%d%d%d", &a, &b, &c);

                Query_gcd(1, 1, N, a, b);

                int ans = Get(ansgcd, c);

                printf("%d\n", ans);

            }

            else {

                scanf("%d%d", &a, &c);

                Change(1, 1, N, a, c);

            }

        }

    }

    return 0;

}

巴特西

HDU_3071 Gcd & Lcm game 【素数分解 + 线段树 + 状压】

一、题目

二、分析

三、AC代码

最新文章

热门文章