30.Boring Queries 可持久化權值線段樹維護區間GCD/LCM

個人Limitの線段樹題單題解主目錄：Limitの線段樹題單 題解目錄_HeartFireY的部落格

給定序列，要求不帶修支援線上查詢區間最小公倍數對1e9+7取模的結果

主席樹不帶修線上維護區間GCD，記錄質因數最後一次出現的位置并消除貢獻

洛谷傳送門：​​CF1422F Boring Queries - 洛谷 | 計算機科學教育新生态 (luogu.com.cn)​​

CF傳送門：​​F. Boring Queries (codeforces.com)​​

題目分析

給定序列，要求支援線上查詢區間最小公倍數對取模的結果，不帶修。

考慮暴力求解的方式：直接合并最小公倍數，但是發現帶取模，無法合并。

但是發現最大公倍數可以轉化為求區間乘積除區間最大公因數。那麼可以想到用區間合并的方式求解，因為最小公倍數時可以兩兩區間進行合并求出的。但是帶取模，我們會發現由于出現了帶模意義下的除法，不能簡單的進行合并。

首先我們寫出區間最小公倍數的表達式：

再轉化為模意義下的表達式：

我們都知道，對于，我們可以對分解質因數，然後求公有因數連乘積，注意共有因數是有重複的。

我們可以将區間公有質因數表示為數對，表示質因數，表示在共有質因數中該因數的出現次數。那麼将共有質因數寫作集合，那麼可以将區間最大公因數寫作：

現在考慮加入一個數字的影響，假設現在有一個長度為的序列，設：

那麼對于單點，答案就是，但是對于區間，我們可以發現要除(最小公倍數式子)。那麼考慮如何消除多乘的貢獻。一個很妙的思路是，固定右端點進行枚舉，我們維護質因子的次幂在左邊最後一次出現的位置，每次插入單點時，邊分解質因數，邊對先前重疊的貢獻(即為區間的組成部分)進行消除。

我們分析上述序列的區間的計算過程，為了友善解釋，設：

• 單點插入葉節點，，号葉子節點上有的貢獻，故
• 不是質數，質因數分解，第一次分解到達，發現之前沒有重複貢獻，不需要消除
• 變為仍不是質數，質因數分解，第二次分解到達，發現之前有重複貢獻，于是對号葉子節點乘消除貢獻
• 單點插入節點到号葉子節點上，号葉子節點上疊加的貢獻

我們可以發現，最終答案就是各葉子節點的累乘。即我們通過對區間分解進行消除達到了消除重複貢獻的效果。

類似的，我們把和交換一下，分析插入順序，發現單個造成的重複貢獻在插入時仍會被消除。

但是我們發現，這樣沒法查詢任意區間。因為消除貢獻的計算會導緻葉節點發生變化。但是我們發現有一個東西很符合我們想要的效果：固定右端點查詢區間，每加入個右端點就會構成新序列，但與先前的序列有較大重疊。那麼顯然我們可以用可持久化權值線段樹維護這個東西。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
// #define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;

namespace ffastIO {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    // inline int read() {
    //  int a = 0, b = 1, c = fetch();
    //  while (!isdigit(c))b ^= c == '-', c = fetch();
    //  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
    //  return b ? a : -a;
    // }
    inline int read(){
        int f = 1, x = 0; char s = getchar(); 
        while(s < '0'||s > '9'){ if(s == '-') f = -1; s = getchar(); } 
        while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
        return x *= f; 
    }
}

using ffastIO::read;

int a[N], n, lastans;
int inv[N << 1], fac[N << 1], root[N], lst[N << 1];

inline int get(int x) { return (x + lastans) % n + 1; }

namespace SegTree{
    int tree[N * 400], lc[N * 400], rc[N * 400], tot;

    inline void push_up(int rt){ tree[rt] = 1ll * tree[lc[rt]] * tree[rc[rt]] % MOD; }

    void update(int &rt, int pre, int l, int r, int x, int num){
        rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], tree[rt] = 1ll * tree[pre] * num % MOD;
        if(l == r) return;
        int mid = l + r >> 1;
        if(mid >= x) update(lc[rt], lc[pre], l, mid, x, num);
        else update(rc[rt], rc[pre], mid + 1, r, x, num);
        push_up(rt);
    }

    int query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1; long long ans = 1;
        if(mid >= L) ans = (1ll * ans * query(lc[rt], l, mid, L, R)) % MOD;
        if(mid < R) ans = (1ll * ans * query(rc[rt], mid + 1, r, L, R)) % MOD;
        return ans;
    }
}


inline void solve(){
    n = read(), lastans = 0;
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++){
        root[i] = root[i - 1];
        int now = a[i];
        while(fac[now]){
            int k = fac[now], t = 1;
            while(!(now % k)){
                t *= k, now /= k;
                if(lst[t]) SegTree::update(root[i], root[i], 1, n, lst[t], inv[k]);
                lst[t] = i;
            }
            SegTree::update(root[i], root[i], 1, n, i, t);
        }
    }
    int q = read();
    while(q--){
        int l = get(read()), r = get(read());
        if(l > r) swap(l, r);
        lastans = SegTree::query(root[r], 1, n, l, r);
        // cout << l << ' ' << r << endl;
        cout << lastans << endl;
    }
}

void init(){
    inv[1] = 1, SegTree::tree[0] = 1;
    for(int i = 2; i < 2 * N - 5; i++){
        inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
        if(!fac[i]){ for(int j = i; j < 2 * N - 5; j += i) fac[j] = i; }
    }
}

signed main(){
    init();
    solve();
    return 0;
}