http://acm.hdu.edu.cn/showproblem.php?pid=3071

#include 
#include 
using namespace std;
const int P[] = {2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const int N = 205011, M = 35;

int l[2*N-1], r[2*N-1];
long long gcd_key[2*N-1]; long long lcm_key[2*N-1];
int left_child[2*N-1], right_child[2*N-1];
int parent[2*N-1]; int total, root;
int bottom[N];  int n, m;
long long num[N];

int a, b ,c, p; long long gcd, lcm;


long long f(int a){
    long long x = 0, y = 1;
    for (int i=0;i<35;i++,y<<=1){
        if (a%P[i]==0){
            x|=y; a/=P[i];
        }
    }
    return x;
}

int g(long long x){
    int a = 1; long long y = 1;
    for (int i=0;i<35;i++,y<<=1){
        if ((x&y)!=0){
            a = (a * P[i]) % p;
            x &=~ y;
        }
    }
    return a;
}



void updata(int now){
    gcd_key[now] = gcd_key[left_child[now]] & gcd_key[right_child[now]];
    lcm_key[now] = lcm_key[left_child[now]] | lcm_key[right_child[now]];
}

void query_gcd(int now){
    if (a<=l[now]&&r[now]<=b){
        gcd = gcd & gcd_key[now];
        return;
    }

    int m = (l[now]+r[now])/2;
    if (a<=m) query_gcd(left_child[now]);
    if (m< b) query_gcd(right_child[now]);
}
void query_lcm(int now){
    if (a<=l[now]&&r[now]<=b){
        lcm = lcm | lcm_key[now];
        return;
    }

    int m = (l[now]+r[now])/2;
    if (a<=m) query_lcm(left_child[now]);
    if (m< b) query_lcm(right_child[now]);
}

void modify(){
    int now = parent[bottom[a]];
    while (now!=-1){
        updata(now); now = parent[now];
    }
}


void build(int &now, int a, int b){
    now = total++;
    l[now] = a; r[now] = b;
    if (a==b){
        gcd_key[now] = lcm_key[now] = num[a];
        bottom[a] = now;
    }
    else {
        int m = (a+b)/2;
        build(left_child[now],a ,m); build(right_child[now],m+1 ,b);
        parent[left_child[now]] = now; parent[right_child[now]] = now;
        updata(now);
    }
}







void init(){
    int a;
    for (int i=1;i<=n;i++){
        scanf("%d", &a); num[i] = f(a);
    }
    total = 0;
    build(root,1,n);
}



int main(){
    //p = 100; cout << g(f(97)) << endl;
    parent[0] = -1; char ch;

    while(scanf("%d%d",&n, &m) == 2){
        init();
        while (m--){
            scanf(" %c", &ch);
            switch(ch){
                case 'C':
                    scanf("%d%d%d",&a, &b);
                    gcd_key[bottom[a]] = lcm_key[bottom[a]] = num[a] = f(b);
                    modify();
                break;
                case 'G':
                    scanf("%d%d%d",&a ,&b, &p);gcd = num[a];
                    query_gcd(root);
                    printf("%d\n", g(gcd));
                break;
                case 'L':
                    scanf("%d%d%d",&a, &b, &p);lcm = num[a];
                    query_lcm(root);
                    printf("%d\n", g(lcm));
            }
        }
    }
}

Posted by xiaodao
Category: 日常