#F. ”简单签到题“

    传统题 1000ms 256MiB

”简单签到题“

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个序列NNA1,A2...ANA_{1},A_{2}...A_{N},请问有多少对[L,R](L<R)[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)Lcm\left (A_{L},A_{L+1}...A_{R} \right )是求ALA_{L}ARA_{R}所有数的最小公倍数
gcd(AL,AL+1...AR)gcd(A_{L},A_{L+1}...A_{R})是求ALA_{L}ARA_{R}所有数的最大公约数
i=LRAi\prod_{i=L}^{R} A_{i}ALA_{L}ARA_{R}的累积

输入格式

第一行包含一个整数 T(1T103)T (1≤T≤10^{3})—测试用例的数量。
每一个测试用例有两行:
第一行一个整数NN表示序列的长度(2N103)(2 \le N \le 10^{3})
第二行NN个整数NN表示序列的元素 A1,A2...ANA_{1},A_{2}...A_{N}(1Ai103)(1 \le A_{i} \le 10^{3})

输出格式

TT行,每行一个整数表示该序列中满足条件[L,R][L,R]的数量

样例

2
3
1 2 3
2
3 9
3
1

解释:
对于第一个样例:
[1,2][1,2]:Lcm(A1,A2)=2Lcm\left (A_{1},A_{2}\right)=2,i=12Ai=2\prod_{i=1}^{2} A_{i}=2
[2,3][2,3]:Lcm(A2,A3)=6Lcm\left(A_{2},A_{3}\right)=6,i=12Ai=6\prod_{i=1}^{2} A_{i}=6
[1,3][1,3]:Lcm(A1,A2,A3)=6Lcm\left(A_{1},A_{2},A_{3}\right)=6,i=13Ai=6\prod_{i=1}^{3} A_{i}=6
对于第二个样例:
[1,2][1,2]:Lcm(A1,A2)=9Lcm\left (A_{1},A_{2}\right)=9,i=12Ai=27\prod_{i=1}^{2} A_{i}=27



TipTip:

$$Lcm\left (a,b \right )=\frac{a\cdot b}{gcd\left (a,b\right )} $$

2024黄冈师范学院第四届『小白杯』ACM程序设计新生赛-热身赛

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2024-12-1 9:30
结束于
2024-12-1 11:00
持续时间
1.5 小时
主持人
参赛人数
52