cfF. Boring Queries

題意：

n個數組a[]，q個詢問，每次詢問區間[l,r]的lcm值
題目要求強制在線
1<=n<=1e5
1<=a<=2e5
1<=q<=1e5

題解：

添加鏈接描述
添加鏈接描述
添加鏈接描述

我們一般求lcm都是直接通過ab/gcd(a,b)來做，但是現在要對所有lcm取模，且a，b都比較大，就不能直接通過這個計算了，我們開始挖掘lcm更深層的內涵。
ab/gcd(a,b)的作用其實是對a，b的每個質因子的冪次都取了max，就是說，如果$a=p_1^{x1}?p_2^{x2}.....?p_n^{xn}$,$b=p_1^{y1}?p_2^{y2}.....?p_n^{yn}$,那么$lcm(a,b)=p_1^{max(x1,y1)}?p_2^{max(x2,y2)}.....?p_n^{max(xn,yn)}$
也就是我們可以通過維護質因子的個數，來求lcm
現在我們開始考慮質因子的個數，因為ai<=2e5，所以對于質因子p，如果$p^2$>2e5,那么它出現的次數只有0/1，那查詢一個區間內除重后的這些數的乘積。為了減少空間開支，我們可以用主席樹來維護這這些質因子，但是一個區間內有可能出現多個相同質因子，該如何處理？
我們參考P1972 [SDOI2009]HH的項鏈中主席樹的操作，對于右端點為r的區間[…,r]，相同數字，我們只維護最靠近r的(對每個因子維護一個最后出現的乘積，這樣就不會重復計算)。

如果$p^2$<2e5,最多只有86個質數，那么可以用87個線段樹來維護區間max,因為本題并沒有涉及修改，rmq問題可以用st表來實現，維護86個RMQ表
復雜度是$O(86?nlogn)$

個人思考：
我感覺分塊不能做，多個數的lcm不是所有數的乘積除以所有數的gcd，就比如4 ，8，3
$O(86?nlogn)$常數偏大，但是能過，還有$O(nlo{g}^{2}n)$的做法，之后更新

代碼：

#include <bits/stdc++.h>using namespace std;const int N= 1e5 + 10, M= 2e5 + 10, mod= 1e9 + 7;int root[N], ls[N * 40], rs[N * 40], sum[N * 40], num;int prime[N], Log[N], inv[M], pre[M], fac[M], a[N], cnt, n, m;vector<int> p[87];bool st[M];struct RMQ {char f[N][18];void init(){for (int j= 1; j < 18; j++) {for (int i= 1; i + (1 << j) - 1 <= n; i++) {f[i][j]= max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}}int query(int l, int r){int s= Log[r - l + 1];return max(f[l][s], f[r - (1 << s) + 1][s]);} } rmq[87];void init() {inv[1]= 1;for (int i= 2; i < M; i++) {inv[i]= 1ll * (mod - mod / i) * inv[mod % i] % mod;if (!st[i]) {prime[++cnt]= i;}for (int j= 1; j <= cnt && 1ll * i * prime[j] < M; j++) {st[i * prime[j]]= 1;if (i % prime[j] == 0) {break;}}}for (int i= 2; i < N; i++) {Log[i]= Log[i / 2] + 1;}for (int j= 1; prime[j] * prime[j] < M; j++) {for (int i= 1; i <= n; i++) {while (a[i] % prime[j] == 0) {a[i]/= prime[j];rmq[j].f[i][0]++;}}rmq[j].init();for (int cur= 1; cur < M; cur*= prime[j]) {p[j].push_back(cur); //第j個質數所對應的各種次冪}}for (int i= 87; i <= cnt; i++) {for (int j= prime[i]; j < M; j+= prime[i]) {fac[j]= prime[i];}} }void build(int& rt, int l, int r) {rt= ++num;if (l == r) {sum[rt]= 1;return;}int mid= l + r >> 1;build(ls[rt], l, mid);build(rs[rt], mid + 1, r);sum[rt]= sum[ls[rt]] * sum[rs[rt]]; }void update(int& rt, int pre, int l, int r, int x, int v) {rt= ++num;ls[rt]= ls[pre];rs[rt]= rs[pre];sum[rt]= 1ll * sum[pre] * v % mod;if (l == r) {return;}int mid= l + r >> 1;if (x <= mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid + 1, r, x, v);} }int query(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return sum[rt];}int ans= 1, mid= l + r >> 1;if (L <= mid) {ans= 1ll * ans * query(ls[rt], l, mid, L, R) % mod;}if (R > mid) {ans= 1ll * ans * query(rs[rt], mid + 1, r, L, R) % mod;}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);for (int i= 1; i <= n; i++) {scanf("%d", &a[i]);}init();build(root[0], 1, n);for (int i= 1; i <= n; i++) {root[i]= root[i - 1];if (!fac[a[i]]) {continue;}update(root[i], root[i], 1, n, i, fac[a[i]]);if (pre[fac[a[i]]]) {update(root[i], root[i], 1, n, pre[fac[a[i]]], inv[fac[a[i]]]); //將上個位置的fac[a[i]]去掉}pre[fac[a[i]]]= i;}scanf("%d", &m);int ans= 0;for (int i= 1, l, r; i <= m; i++) {scanf("%d %d", &l, &r);l= (ans + l) % n + 1, r= (ans + r) % n + 1;if (l > r) {swap(l, r);}ans= 1;for (int j= 1; j <= 86; j++) {ans= 1ll * ans * p[j][rmq[j].query(l, r)] % mod;}ans= 1ll * ans * query(root[r], 1, n, l, r) % mod;printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的cfF. Boring Queries的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。