推到后面被卡常了就完全不会。。。神qwaszx！真不知道这些神仙是如何想到做法的
这题的难点在于很多地方不能随便取模，而且值域特别大
写篇题解总结一下。
众所周知（其实也很好证明，我就不证了）
\[\operatorname{lcm}(a,b)=a\dfrac{b}{\gcd(a,b)} \]考虑如何把那一堆 \(\operatorname{lcm}\) 搞成可以乘的形式，这样就可以边乘边取模了
\[b_i=\dfrac{a_i}{\gcd(a_i,\prod_{j>i}b_j)}\\ \operatorname{lcm}(a_l,a_{l+1},\dots,a_r)=\prod_{i=l}^{r} b_i\\ \]（上面就是连续使用最上头那个性质的结果）
然后我卡住了，这个式子还是没什么用，那个 \(\prod_{j>i}b_j\) 大的离谱
瞟了题解，可以每次往右扩展一个数 \(a_k\) 。
这时候 \(b_k=a_k,b_i\to b_i'\) （显然 \(b'_i\le b_i\)），令 \(c_i=\dfrac{b_i}{b'_i}\) ，那么 \(\prod c_i\le a_k\) ，因为是 \(\operatorname{lcm}\) 。这样就有了一个可以 \(\pi\) 的东西（别问我为啥写 \(\pi\) ，因为我就是这么读的）
首先
\[b'_i=\dfrac{b_i}{\gcd(b_i,\prod_{j>i}b'_j)} \]就是倒着求 \(b'\) ，前面因为多了 \(a_k\) ，已经消掉的因子就不用统计了
那个 \(\prod b'_i\) 仍然太大，但是我们可以通过求出 \(c_i\) 来修改每一个 \(b_i\)
\[c_i=\gcd(b_i,\dfrac{a_k}{\prod_{j>i}c_j}) \]\(c_i\) 这个式子的来源还是约掉已经约掉的，留下有用的。
因为 \(\prod c_i\) 不会超long long，所以直接 \(\pi\) 就行了
这样就可以 $O(Tn^2\log V) $ 解决这题了。
可惜出题人并不认为你解决了，卡掉了这个复杂度，你 TLE 90 了。
可是 \(\color{black}{\texttt{c}}\color{red}{\texttt{yn2006}}\) 也是这个复杂度没卡常就过去了。这就是神仙与蒟蒻的差别。
我尝试搞些科技来卡常
瓶颈在于有 \(n^2\) 次 \(\gcd\) ，这让我想到了一个叫做“快速gcd”的东西，大致思路是辗转相减，二进制优化
LL gcd(LL x,LL y){
if(!x||!y)return x|y;
if(!(x&1)&&!(y&1))return gcd(x>>1,y>>1)<<1;
if(!(x&1))return gcd(x>>1,y);
if(!(y&1))return gcd(x,y>>1);
return gcd(abs(x-y),min(x,y));
}
然后发现多 TLE 了一个点 什么鬼哦，龟速gcd
自闭了去看 qwaszx 的题解。
他就是利用了一个性质来减少 \(\gcd\) 的次数 然而这个性质在我以前验题的时候自己想到过
看看我们是如何求 \(c_i\) 的
\[c_i=\gcd(b_i,\dfrac{a_k}{\prod_{j>i}c_j}) \]所以不是 \(1\) 的 \(c_i\) 至多 \(\log V\) 个，因为每一个不是 \(1\) 的 \(c_i\) 都会导致 \(a_k\) 至少除以 \(2\) ，所以我们只需要判断 \(c_i\) 是否是 \(1\) ，于是求 \(\gcd\) 的次数变成了 \(n\log V\)
如何快速判断 \(c_i\) 的值呢？
首先有俩性质：
\[\gcd(xy,a)\not=\gcd(y,a)\Leftrightarrow \gcd(xy,a) \not\mid y \]这个逻辑表达式的两边只要有一个满足，就说明存在质因数 \(p\) 满足 \(\min(p_x+p_y,p_a)>\min(p_y,p_a)\) （其中 \(p_i\) 表示 \(p\) 在 \(i\) 中的最高次数） 那么另一边必然成立
\[y\mod \gcd(xy,a)\not=0\Leftrightarrow (y\mod a)\mod \gcd(xy,a) \not =0 \]这个非常显然， \(a\) 是 \(\gcd(xy,a)\) 的倍数，而 \(x\mod a\equiv (x-ka)\mod a\)
令 \(s_i=\prod_{j=i}^{k}b'_j\)
套用上述两个性质可得
\[\gcd(s_i,a_k)\not=\gcd(s_{i+1},a_k)\Leftrightarrow \gcd(s_i,a_k)\not\mid s_{i+1}\Leftrightarrow (s_{i+1}\mod a_k)\mod \gcd(s_i,a_k) \not= 0 \]所以每次扩展时算出 \(s_i\mod a_k\) ，记录 \(\gcd(s_i,a_k)\) ，取模判一下是否重算 \(\gcd\) 即可
但是还有个问题，就是 \(s_i\mod a_k\) 怎么处理，如果龟速乘会多个 \(\log V\) ，复杂度是 \(O(T(n\log^3 V+n^2))\)
\(n\) 只有 \(300\) ，但是 \(\log V\) 只有 \(60\) ，比原来的复杂度还劣。。。
又是一个科技：光速乘，它是 \(O(1)\) 计算 long long 级别的取模乘法的
LL mul(LL a,LL b,LL P){
LL res=a*b-(LL)((long double)a/P*b+0.5)*P;
return res<0?res+P:res;
}
__int128 也行，但是NOIP用不了啊。。。
我感觉上面那个光速乘挺牛逼的，跑了一下 \((2^{60}-1)(2^{60}+1)\mod 2^{60}\) 居然跑对了，精损并没有想象中那么严重
AC代码：
#define N 305
#define mod 1000000007
int n,q,ans[N][N];
LL a[N],b[N],s[N];
LL mul(LL a,LL b,LL P){
LL res=a*b-(LL)((long double)a/P*b+0.5)*P;
return res<0?res+P:res;
}
void init(){
for(int i=1;i<=n;++i){
b[i]=a[i],s[i]=1;
for(int j=i-1;j>=1;--j)s[j]=mul(s[j+1],b[j],a[i]);
LL t=__gcd(s[1],a[i]);
for(int j=1;j<i;++j){
if(s[j+1]%t){
LL gcd=__gcd(t,s[j+1]);
b[j]/=t/gcd,t=gcd;
}
}
ans[i][i]=a[i]%mod;
for(int j=i-1;j>=1;--j)ans[j][i]=1ll*ans[j+1][i]*(b[j]%mod)%mod;
}
}
void Main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
init();
while(q--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",ans[l][r]);}
}
signed main(){for(int T=read();T;--T)Main();}
TLE的
#define N 305
#define mod 1000000007
int n,q,ans[N][N];
LL a[N],b[N],c[N];
LL gcd(LL x,LL y){return !y?x:gcd(y,x%y);}
void init(){
for(int i=1;i<=n;++i){
b[i]=a[i],c[i]=1;
for(int j=i-1;j>=1;--j){
c[j]=gcd(b[j],a[i]/c[j+1]);
b[j]/=c[j];
c[j]*=c[j+1];
}
ans[i][i]=a[i]%mod;
for(int j=i-1;j>=1;--j)ans[j][i]=1ll*ans[j+1][i]*(b[j]%mod)%mod;
}
}
void Main(){
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
init();
while(q--){int l,r;scanf("%lld%lld",&l,&r);printf("%lld\n",ans[l][r]);}
}
signed main(){for(int T=read();T;--T)Main();}