30.Boring Queries 可持久化权值线段树维护区间GCD/LCM

30.Boring Queries 可持久化权值线段树维护区间GCD/LCM

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求不带修支持在线查询区间最小公倍数对1e9+7取模的结果

主席树不带修在线维护区间GCD，记录质因数最后一次出现的位置并消除贡献

洛谷传送门：CF1422F Boring Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. Boring Queries (codeforces.com)

题目分析

给定序列，要求支持在线查询区间最小公倍数对$1e9+7$取模的结果，不带修。

考虑暴力求解的方式：直接合并最小公倍数，但是发现带取模，无法合并。

但是发现最大公倍数可以转化为求区间乘积除区间最大公因数。那么可以想到用区间合并的方式求解，因为最小公倍数时可以两两区间进行合并求出的。但是带取模，我们会发现由于出现了带模意义下的除法，不能简单的进行合并。

首先我们写出区间最小公倍数的表达式：
$$ans(l,r)=\frac{{\prod }_{i=l}^r{a}_i}{{\gcd }_{i=l}^r{a}_i}$$
再转化为模意义下的表达式：
$$ans(l,r)\mathrm{mod}x=\prod _{i=l}^r{a}_i\times (\underset{i=l}{\overset{r}{\gcd }}{a}_i{)}^{-1}$$
我们都知道，对于${\gcd }_{i=l}^r{a}_i$，我们可以对$a_i(1\le i\le n)$分解质因数，然后求公有因数连乘积，注意共有因数是有重复的。

我们可以将区间公有质因数表示为数对$(p_i,t_i)$，$p_i$表示质因数，$t_i$表示在共有质因数中该因数的出现次数。那么将共有质因数写作集合$\{(p_1,t_1),(p_2,t_2),\dots ,(p_i,t_i)\}$，那么可以将区间最大公因数写作：
$$\underset{i=l}{\overset{r}{\gcd }}{a}_i=p_1^{t_1}\times p_2^{t_2}\times \cdots \times p_i^{t_i}\times \dots$$
现在考虑加入一个数字的影响，假设现在有一个长度为$2$的序列$a_1,a_2，a_3$，设：
$$\begin{gathered} a_1=p_1 \\ {a}_2=p_1\ast p_1\ast p_1 \\ {a}_3=p_1\ast p_1\ast p_1\ast p_1\ast p_1 \end{gathered}$$
那么对于单点$1$，答案就是$p_1$，但是对于区间$[1,2]$，我们可以发现要除$p_1$(最小公倍数式子)。那么考虑如何消除多乘的贡献。一个很妙的思路是，固定右端点进行枚举，我们维护质因子的$k$次幂在左边最后一次出现的位置，每次插入单点时，边分解质因数，边对先前重叠的贡献(即为区间$GCD$的组成部分)进行消除。

我们分析上述序列的区间$[1,2]$的计算过程，为了方便解释，设$p_1=2$：

• 单点$a[1]$插入$1$叶节点，$root[1]=1$，$1$号叶子节点上有$2$的贡献，故$lst[2]=1$
• $a[2]$不是质数，质因数分解，第一次分解到达$2\ast 2=4$，发现之前没有重复贡献$(lst[4]=0)$，不需要消除
• $a[2]$变为$4$仍不是质数，质因数分解，第二次分解到达$2$，发现之前有重复贡献$lst[1]$，于是对$1$号叶子节点乘$2^{-1}$消除贡献
• 单点插入$a[2]$节点到$2$号叶子节点上，$2$号叶子节点上叠加$8$的贡献

我们可以发现，最终答案就是各叶子节点的累乘。即我们通过对区间$GCD$分解进行消除达到了消除重复贡献的效果。

类似的，我们把$a_1$和$a_2$交换一下，分析插入顺序，发现单个$p_1$造成的重复贡献在插入$a_2$时仍会被消除。

但是我们发现，这样没法查询任意区间。因为消除贡献的计算会导致叶节点发生变化。但是我们发现有一个东西很符合我们想要的效果：固定右端点查询区间，每加入$1$个右端点就会构成新序列，但与先前的序列有较大重叠。那么显然我们可以用可持久化权值线段树维护这个东西。

在质因数分解的时候，记录质因数幂次最后出现的位置，并判断消除先前的贡献。分解完后加入单点的分子乘积贡献。查询时$[l,r]$从$root[r]$进入查询即可。这里有一点很重要的：当你消除上个数的贡献的时，上个数的之前不会再出现对上个数的重复贡献，也就是每个新插入右端点的重复贡献仅与上次质因子幂次出现的位置有关。

由于开点次数很多，因此很卡空间。如果用空间可回收的版本可能效果会更好。

Code

#include 
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100