出题人喜欢最小公倍数 (lcm),他提供了一个数列 a1,a2,…,an,并给出了一些 x,希望你对每个 x 都求出以下式子的值:
i=1minn−x+1lcm(ai,ai+1,…,ai+x−1)
简单来说求出这个数列所有长度为 x 的连续子序列的最小公倍数中的最小值(简单来说?
数列 ai 的长度为 n,一个 x 就是一次询问,共有 m 次询问,并有以下限制:
1≤n≤2×104 1≤m≤106 1≤ai≤60 1≤x≤n
题解
对于一个数 x,可以将其分解质因数:x=p1b1×p2b2×…×pkbk,其中 pi 指第 i 个素数。于是 x 就可以表示为一个数列 b 。用这种表示方法,可以很方便地表示最小公倍数。假设有两个数 x=p1b1×p2b2×…×pkbk 和 y=p1c1×p2c2×…×pkck,那么就有:
最后是查询,对于每一个 x 都重新遍历一遍数列是肯定会 TLE 的,所以要先将每一个区间长度的结果处理出来。大概过程是这样的:创建两个 “指针” l 和 r 。一开始,l 和 r 都指向第一个元素,之后让 r 不断向后移动,直至指向第一个 lcm 值lcm(al,al+1,…,ar) 与之前的 lcm 值不同的元素,并用之前的 lcm 值更新 ansr−l 的值。再向右移动 r 并如此更新,直至数列尾后元素。之后 l 和 r 同时指向第二个元素,重复上述操作,再同时指向第三个元素…… 直至同时指向数列的尾部元素。
int lg2[maxn], pw2[lg2maxn], ansi[maxn]; vi rmq[maxn][lg2maxn], ans[maxn], p; vector<double> lnp;
voidinit() { for (int i = 2; i != maxn; ++i) lg2[i] = lg2[i >> 1] + 1; for (int i = 0; i != lg2maxn; ++i) pw2[i] = 1 << i; for (int i = 2; i <= 60; ++i) { bool prime = true; for (int j = 2; prime && j * j <= i; ++j) if (!(i % j)) prime = false; if (prime) p.push_back(i), lnp.push_back(log((double)i)); } fill(ans, ans + maxn, vi(p.size(), 7)); }
vi lcm(const vi& a, const vi& b) { vi res(p.size()); for (int i = 0, i_ = p.size(); i != i_; ++i) res[i] = max(a[i], b[i]); return res; }
vi intvlcm(int l, int r) { int s = lg2[r - l]; returnlcm(rmq[l][s], rmq[r - pw2[s]][s]); }
vi itov(int x) { vi res(p.size(), 0); for (int i = 0, i_ = p.size(); i != i_; ++i) while (!(x % p[i])) ++res[i], x /= p[i]; return res; }
intvtoi(const vi& x) { ll res = 1ll; for (int i = 0, i_ = p.size(); i != i_; ++i) for (int j = x[i]; j--;) res = (res * p[i]) % mod; return res; }
boolcmp(const vi& a, const vi& b) { double x = 0.0, y = 0.0; for (int i = 0, i_ = p.size(); i != i_; ++i) x += lnp[i] * a[i], y += lnp[i] * b[i]; return x < y; }
intmain() { init(); int n, q; scanf("%d%d", &n, &q); for (int i = 0, t; i != n; ++i) scanf("%d", &t), rmq[i][0] = itov(t); for (int j = 1; j <= lg2[n]; ++j) for (int i = n - pw2[j]; i != -1; --i) rmq[i][j] = lcm(rmq[i][j - 1], rmq[i + pw2[j - 1]][j - 1]); //////////////////////////////// for (int l = 0; l != n; ++l) { vi cur = rmq[l][0]; for (int r = l; r != n;) { cur = lcm(cur, rmq[r][0]); for (int k = lg2[n - r]; k != -1; --k) if (r + pw2[k] <= n && lcm(cur, rmq[r][k]) == cur) r += pw2[k]; ans[r - l] = min(ans[r - l], cur, cmp); } } //////////////////////////////// for (int x; q--;) { scanf("%d", &x); printf("%d\n", ansi[x] ? ansi[x] : (ansi[x] = vtoi(ans[x]))); } }