Problem
(n) 个数，每个数为 (a_i)，有 (Q) 次询问，每次询问 ([l,r])，求 (LCM_{i=l}^r a_i)。总共 (T) 组数据。
数据范围：(1leq n, Q, Tleq 300)， (1leq a_ileq 2^{60})。
Solution
首先暴力分解质因数然后搞的最多只有 (40) 分。
考虑另一种暴力：将 (LCM) 表示成若干个数的乘积以避免数字太大。记 (lcm_{l,r}=LCM_{i=l}^r)，我们用 (r-l+1) 个数 (b_i) 的乘积表示 (lcm_{l,r})。考虑纳入 (a_{r+1})，注意到 (lcm_{l,r+1}=dfrac{lcm_{l,r} imes a_{r+1}}{(lcm_{l,r},a_{r+1})})，增加的因子为 (dfrac{a_{r+1}}{(lcm_{l,r},a_{r+1})})，将其记为 (b_{r+1})，利用 ((a,b)=(amod b,b)) 求解。通过这样我们可以用 (mathcal O(Tn^3log V)) 的复杂度求解，其中 (V) 为 (a_i) 的最大值。
使用分治优化：考虑求解(lcm_{i,j})，其中 (lleq ileq mid,mid<jleq r)。首先求出来 (lcm_{l,mid}=prod_{i=l}^{mid}b_i^{[L]}) 和 (lcm_{mid+1, r}=prod_{i=mid+1}^rb_{i}^{[R]})。注意这里求解 (b^{[L]}) 从右往左，(b^{[R]}) 从左往右，这样满足 (lcm_{i,mid}=prod_{j=i}^{mid}b_j^{[L]})，(lcm_{mid+1,i}=prod_{j=mid+1}^ib_j^{[R]})。
接下来将 (lcm_{i,mid}) 逐个因子地合并到右边。从 (mid) 往 (l)，每次枚举一个因子 (b_i^{[L]})，让其从左往右继续使用 ((A,prod_i B_i))， 对 (b_j^{[R]}) 消公约数。此时可以求出 (Ans_{i,j}=prod _iA_iprod_i B_i)。复杂度 (mathcal O(Tn^2log V))。
使用技巧将复杂度降成 (mathcal O(Tn(n+log nlog V)))。发现复杂度瓶颈在求 (Ans_{i,j}) 这里，是由于求 GCD 的缘故。采用下列方法将复杂度由 一次 (mathcal O(nlog V)) 降成 (mathcal O(log V))。注意到这里我们实际上要做的是这样的过程
t = b[i];
for j = mid+1 -> r
d = (t, b[j]);
t = t / d;
b[j] = b[j] / d;
这里 (t) 约分不超过 (log b_i) 次，说明只有 (leqlog b_i) 次 (d e 1)。令 (c_j=prod_{mid<kleq j}b_k)，则 (prod_{mid<kleq j}d_k=(b_i, c_k))，(d_k) 是每次约分的值。记 (G=(b_i,c_r))，当第一次遇到 (b_j mod G e 0) 时，必有 ((b_i,b_j) e (b_i,b_{j+1}))，利用 (G'=(G, c_j)) 得到约分的 (d_j=dfrac G{G'})。如此利用下去总 GCD 复杂度仍然为 (mathcal O(log G)leqmathcal O(log V))。加上分治的 (log n)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef long long LL;
const int N = 305, P = 1e9 + 7;
int T, n, Q, ans[N][N];
LL a[N], b[N], c[N];
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL mul(LL a, LL b, LL mod) {
LL t = a * b - (LL)((long double)a / mod * b + 0.5) * mod; t %= mod;
return t < 0 ? t + mod : t;
}
void solve(int l, int r) {
if (l == r) { ans[l][r] = a[l] % P; return; }
int mid = l + r >> 1;
solve(l, mid), solve(mid + 1, r);
for (int i = mid; i >= l; i--) {
LL t = 1;
for (int j = mid; j > i; j--) t = mul(t, b[j], a[i]);
b[i] = a[i] / gcd(a[i], t);
}
for (int i = mid + 1; i <= r; i++) {
LL t = 1;
for (int j = mid + 1; j < i; j++) t = mul(t, b[j], a[i]);
b[i] = a[i] / gcd(a[i], t);
}
int s = 1;
for (int i = mid; i >= l; i--) {
c[mid] = 1;
for (int j = mid + 1; j <= r; j++) c[j] = mul(c[j - 1], b[j], b[i]);
LL G = gcd(c[r], b[i]);
for (int j = r; j > mid; j--)
if (c[j - 1] % G) {
LL d = gcd(G, c[j - 1]);
b[j] /= G/d, G = d;
}
s = b[i] % P * s % P;
int s2 = s;
for (int j = mid + 1; j <= r; j++)
ans[i][j] = s2 = b[j] % P * s2 % P;
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
solve(1, n);
for (int i = 1; i <= Q; i++) {
int l, r; scanf("%d%d", &l, &r);
printf("%d
", ans[l][r]);
}
}
return 0;
}