最暴力的做法显然是直接对 (a_i) 算与之前的数的 ( ext{lcm}) 的答案，将之前的 $ ext{lcm} $ 写成之前每次增大数 (b_i) 的乘积的形式，可以先对 (a_i) 取模之后求 ( ext{gcd})。
考虑分治。
先将前后缀求出来记为 $b $，我们现在需要算的是 (gcd (prod_{ql}^{mid} b_i ,prod_{mid}^{qr},b_i )) 。
显然，我们暴力枚举两个数的 ( ext{gcd}) ，可以做到 (Tn^2*log V)。
能不能做到更优？
考虑那个 (log V) 其实因为 (gcd) 每次都跑满了。我们想要让它变成均摊下来总共一个 $log $。
我们记录 (c_i) 为 ( ext{mid} + 1 , i) 的 (b) 的乘积。( ext{ql}) 从 ( ext{mid}-1) 移动到 ( ext{l}) 的时候，相当于每次在所有右边部分之前加入一个 (b_l) 。我们需要求出新的 (b'_i) 。考虑 ( ext{lcm}(b_l, c_{i+1})/ ext{lcm}(b_l,c_i) = b'_i) ，简单化简，有：
[frac {b_{i+1}} {gcd(c_{i+1},b_l)/gcd(c_i,b_l)} = b'_i
]
考虑 $gcd(c_{i+1},b_l)= gcd(c_{i+1},c_i,b_l) $。
我们可以用 (gcd(c_i+1,b_l)) 和 (c_i) 取 最大公因数，即可算出新的 (gcd(c_i+1, b_l))。
可以分析出这里是每次移动 (l) 均摊一个 (log) 的。
于是复杂度变成了 (Tn^2) 。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 610;
int n;
ll gcd(ll x,ll y){
return y?gcd(y,x%y):x;
}
ll a[N], b[N], c[N];
ll mul(ll x,ll y,ll mo){
y%=mo;
ll t=x*y-(ll)((long double)x/mo*y+1e-9)*mo;
return t<mo?t+mo:t;
}
const int mod = 1e9+7;
int ans[N][N];
void solve(int l,int r){
if(l==r){ans[l][l]=a[l]%mod;return;}
int mid = (l+r)>>1;
solve(l,mid), solve(mid+1,r);
for(int i=mid;i>=l;i--){
ll S = 1; for(int j=i+1;j<=mid;j++) S = mul(S, b[j], a[i]);
b[i] = a[i]/gcd(S,a[i]);
}
for(int i=mid+1;i<=r;i++){
ll S = 1; for(int j=i-1;j>mid;j--) S = mul(S, b[j], a[i]);
b[i] = a[i]/gcd(S,a[i]);
}
int sleft = 1, srgt = 1;
for(int i=mid;i>=l;i--){
sleft = b[i]%mod*sleft%mod;
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-1;j>=mid;j--){
// lcm(c[i+1],b) / lcm(c[i],b) = b[i]
// b[i+1] / (gcd(c[i+1],b)/gcd(c[i],b)) = b[i]
// gcd(c[i], b) = gcd(gcd(c[i+1],b), c[i])
ll ng = gcd(c[j], G);
b[j+1]/=(G/ng);
G = ng;
}
srgt = sleft;
for(int j=mid+1;j<=r;j++){
ans[i][j] = srgt = b[j]%mod*srgt%mod;
}
}
}
void Main()
{
int Q;scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
solve(1,n);
while(Q--){
int l,r;scanf("%d%d",&l,&r);
printf("%d
",ans[l][r]);
}
}
int main()
{
int T;cin >> T;
while(T--){
Main();
}
}