上海微信网站建设公司,wordpress文章如何搬家,建站网站赚钱吗,品牌网站建设有哪些功能cfF. Boring Queries
题意#xff1a;
n个数组a[]#xff0c;q个询问#xff0c;每次询问区间[l,r]的lcm值 题目要求强制在线 1n1e5 1a2e5 1q1e5
题解#xff1a;
添加链接描述 添加链接描述 添加链接描述
我们一般求lcm都是直接通过ab/gcd(a…cfF. Boring Queries
题意
n个数组a[]q个询问每次询问区间[l,r]的lcm值 题目要求强制在线 1n1e5 1a2e5 1q1e5
题解
添加链接描述 添加链接描述 添加链接描述
我们一般求lcm都是直接通过ab/gcd(a,b)来做但是现在要对所有lcm取模且ab都比较大就不能直接通过这个计算了我们开始挖掘lcm更深层的内涵。 ab/gcd(a,b)的作用其实是对ab的每个质因子的幂次都取了max就是说如果ap1x1∗p2x2.....∗pnxnap_{1}^{x1}*p_{2}^{x2}.....*p_{n}^{xn}ap1x1∗p2x2.....∗pnxn,bp1y1∗p2y2.....∗pnynbp_{1}^{y1}*p_{2}^{y2}.....*p_{n}^{yn}bp1y1∗p2y2.....∗pnyn,那么lcm(a,b)p1max(x1,y1)∗p2max(x2,y2).....∗pnmax(xn,yn)lcm(a,b)p_{1}^{max(x1,y1)}*p_{2}^{max(x2,y2)}.....*p_{n}^{max(xn,yn)}lcm(a,b)p1max(x1,y1)∗p2max(x2,y2).....∗pnmax(xn,yn) 也就是我们可以通过维护质因子的个数来求lcm 现在我们开始考虑质因子的个数因为ai2e5所以对于质因子p如果p2p^2p22e5,那么它出现的次数只有0/1那查询一个区间内除重后的这些数的乘积。为了减少空间开支我们可以用主席树来维护这这些质因子但是一个区间内有可能出现多个相同质因子该如何处理 我们参考P1972 [SDOI2009]HH的项链中主席树的操作对于右端点为r的区间[…,r]相同数字我们只维护最靠近r的(对每个因子维护一个最后出现的乘积这样就不会重复计算)。
如果p2p^2p22e5,最多只有86个质数那么可以用87个线段树来维护区间max,因为本题并没有涉及修改rmq问题可以用st表来实现维护86个RMQ表 复杂度是O(86∗nlogn)O(86*nlogn)O(86∗nlogn)
个人思考 我感觉分块不能做多个数的lcm不是所有数的乘积除以所有数的gcd就比如4 83 O(86∗nlogn)O(86*nlogn)O(86∗nlogn)常数偏大但是能过还有O(nlog2n)O(nlog^2n)O(nlog2n)的做法之后更新
代码
#include bits/stdc.husing 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;vectorint 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;
}
