10.14 JZPLCM

题意

长为\(N\)的序列，\(Q\)次询问，每次询问\([l,r]\)的lcm

解法

可以发现\([l,r]\)的lcm实质上是把\(l\)到\(r\)的所有数进行质因数分解后，对于每个质因子的指数取最大值

但是最大值这个条件不好维护，考虑把贡献拆开，即对于一个质因子的幂\(p^k\)，我们把它拆成\(k\)份，分别为\(p,p^1,p^2,p^3...p^k\)，每一份的贡献均为\(p\)

因此对于每个数我们都这样进行处理，把一个数拆成一段区间，可以证明拆完所有数后区间的长度是\(O(n\log n)\)级别的

这样，在查询\([l,r]\)这段区间时，我们只要查询\(l\)对应的左端点与\(r\)对应的右端点这一个区间内只出现一次的数的乘积即可（这里的乘积指的是出现一次的数作出的贡献）

这是因为如果LCM中有\(p^k\)这一质因子的幂，那么它一定会被拆成\(k\)份，每一份的贡献为\(p\)，而对于其他比\(k\)小的幂，由于是求区间内的不同数，其贡献一定会被忽略

维护区间内不同数以及它们贡献的乘积用离线+树状数组即可，参考\(\tt{HH}\)的项链，即每次添加一个数，把它上一次出现的位置还原：这样能使得对于同一右端点，每个数出现的位置一定最靠右

代码

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 10;
const int mod = 1e9 + 7;

int read();

struct node { int Id, l; };

int N, M;

int func[MAX_N << 1], val[MAX_N << 1], top;
int le[MAX_N], ri[MAX_N], lst[MAX_N << 1], pos[MAX_N << 1];

int pri[MAX_N], mn[MAX_N], cnt;
bool is[MAX_N];

int ans[MAX_N];
vector<node> Q[MAX_N << 1];

inline int fsp(int x, int y = mod - 2) {
    int res = 1;
    for (; y; x = 1LL * x * x % mod, y >>= 1)
        if (y & 1)  res = 1LL * res * x % mod;  
    return res;
}

struct BIT {
    int c[MAX_N << 1];
    
    void init() { for (int i = 1; i <= top; ++i)  c[i] = 1; }
    
    void inc(int x, int v)  {
        for (; x && x <= top; x += x & -x)  c[x] = 1LL * c[x] * v % mod;    
    }
    void dec(int x, int v) {
        v = fsp(v);
        for (; x && x <= top; x += x & -x)  c[x] = 1LL * c[x] * v % mod;
    }
    int ask(int x, int res = 1) {
        for (; x; x -= x & -x)  res = 1LL * res * c[x] % mod;
        return res;
    } 
    int query(int l, int r) {
        return 1LL * ask(r) * fsp(ask(l)) % mod;            
    }
} tr;

void sieve() {
    int lim = (int)1e6;
    for (int i = 2; i <= lim; ++i) {
        if (!is[i])  pri[++cnt] = i, mn[i] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= lim; ++j) {
            is[i * pri[j]] = true, mn[i * pri[j]] = pri[j];
            if (i % pri[j] == 0)  break;
        }
    }
}

void divide(int x, int i) {
    if (x == 1) {
        ++top;
        le[i] = ri[i] = top, func[top] = val[top] = 1;
        return;
    }
    le[i] = top + 1;
    while (x ^ 1) {
        int s = mn[x], pw = mn[x];
        while (x % s == 0) {
            func[++top] = pw, val[top] = s;
            x /= s, pw *= s;
        }
    }
    ri[i] = top;
}

int main() {
    
    sieve();
    
    N = read(), M = read();
    
    for (int i = 1; i <= N; ++i)  divide(read(), i);
    
    for (int i = 1; i <= top; ++i) {
        lst[i] = pos[func[i]];
        pos[func[i]] = i;   
    }
    
    for (int i = 1; i <= M; ++i) {
        int l = read(), r = read();
        Q[ri[r]].push_back((node){i, le[l]});
    }
    
    tr.init();
    for (int i = 1; i <= top; ++i) {
        tr.inc(i, val[i]);
        if (lst[i])  tr.dec(lst[i], val[i]);
        for (int j = 0; j < (int)Q[i].size(); ++j) {
            int Id = Q[i][j].Id, l = Q[i][j].l;
            ans[Id] = tr.query(l - 1, i);
        }
    }
    
    for (int i = 1; i <= M; ++i)  printf("%d\n", ans[i]);
    
    return 0;
}

int read() {
    int x = 0, c = getchar();
    while (!isdigit(c))  c = getchar();
    while (isdigit(c))   x = x * 10 + c - 48, c = getchar();
    return x;   
}

10.14 JZPLCM

原文：https://www.cnblogs.com/VeniVidiVici/p/11677110.html