该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给你一个序列N为A1,A2...AN,请问有多少对[L,R](L<R)满足
$$Lcm\left (A_{L},A_{L+1}...A_{R}\right)
\le\prod_{i=L}^{R} A_{i}
$$
Lcm(AL,AL+1...AR)是求AL到AR所有数的最小公倍数
gcd(AL,AL+1...AR)是求AL到AR所有数的最大公约数
∏i=LRAi是AL到AR的累积
输入格式
第一行包含一个整数 T(1≤T≤103)—测试用例的数量。
每一个测试用例有两行:
第一行一个整数N表示序列的长度(2≤N≤103)
第二行N个整数N表示序列的元素
A1,A2...AN(1≤Ai≤103)
输出格式
共T行,每行一个整数表示该序列中满足条件[L,R]的数量
样例
2
3
1 2 3
2
3 9
3
1
解释:
对于第一个样例:
[1,2]:Lcm(A1,A2)=2,∏i=12Ai=2
[2,3]:Lcm(A2,A3)=6,∏i=12Ai=6
[1,3]:Lcm(A1,A2,A3)=6,∏i=13Ai=6
对于第二个样例:
[1,2]:Lcm(A1,A2)=9,∏i=12Ai=27
Tip:
$$Lcm\left (a,b \right )=\frac{a\cdot b}{gcd\left (a,b\right )}
$$