Link
首先考虑这样表示答案：\(ans_{l,r}=\prod\limits_{i=l}^rb_i\)，其中\(b_i=\frac{a_i}{\gcd(a_i,\prod\limits_{j=l}^{i-1}b_j)}=\frac{a_i}{\gcd(a_i,(\prod\limits_{j=l}^{i-1}b_j)\bmod a_i)}\)。
那么这样我们就可以得到一个\(O(n^2qT\log a)\)的暴力算法。
现在有多组询问，我们考虑预处理所有答案。
同样的，假设我们现在固定右端点为\(r\)，我们希望能够处理出一个\(\{b\}\)，使得\(ans_{l,r}=\prod\limits_{i=l}^rb_i\)，即\(b_i=\frac{a_i}{\gcd(a_i,\prod\limits_{j=i+1}^rb_j)}\)。
那么我们插入\(a_i\)时，需要做的操作就是\(b_i\leftarrow a_i\)，然后从后往前更新\(b_j\leftarrow\frac{b_j}{\gcd(b_j,\prod\limits_{k=j+1}^ib_k)}(j<i)\)。
设\(b_j\leftarrow\frac{b_j}{c_j}\)，那么\(c_j=\gcd(\frac{b_i}{\prod\limits_{k=j+1}^ic_k},b_j)\)。
这样做的时间复杂度为\(O(Tn^2\log n)\)，无法通过。
考虑优化\(\gcd\)，我们知道插入\(a_i\)时，\(c_j\)只有\(O(\log a)\)个不为\(1\)。
令\(s_j=\prod\limits_{k=j}^{i-1}b_k\bmod b_i\)，那么\(\prod\limits_{k=j}^{i-1}c_k=\gcd(s_j,b_i)\)。
从前往后利用取模判断\(\gcd(s_j,b_i)\)是否减小来更新即可。

#include<cctype>
#include<cstdio>
using i64=long long;
const int N=307,P=1000000007;
int ans[N][N];i64 a[N],b[N];
i64 read(){i64 x=0;int c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
i64 mul(i64 a,i64 b,i64 p){i64 d=a*b-(i64)((long double)a/p*b+0.5)*p;return d<0? d+p:d;}
i64 gcd(i64 n,i64 m){return !n||!m? n|m:gcd(m,n%m);}
int main()
{
    for(int T=read(),n,q;T;--T)
    {
	n=read(),q=read();
	for(int i=1;i<=n;++i)
	{
	    a[i]=read(),b[i]=1,ans[i][i]=a[i]%P;
	    for(int j=i-1;j;--j) b[j]=mul(a[j],b[j+1],a[i]);
	    i64 g=gcd(b[1],a[i]),t;
	    for(int j=1;j<i;++j) if((t=b[j+1]%g)) t=gcd(t,g),a[j]/=g/t,g=t;
	    for(int j=i-1;j;--j) ans[i][j]=1ll*ans[i][j+1]*(a[j]%P)%P;
	}
	for(int l,r;q;--q) l=read(),r=read(),printf("%d\n",ans[r][l]);
    }
}