http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1339. JZPLCM(顾昱洲)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:226   AC次数:46   平均分:36.79
将本题分享到:
   
 
问题描述
  给定一长度为n的正整数序列a,有q次询问,每次询问一段区间内所有数的lcm(即最小公倍数)。由于答案可能很大,输出答案模1000000007。
输入格式
  第一行,两个整数,n, q,分别表示数列长度和询问个数。
  下面n行,每行一个整数,第i行的整数为ai
  下面q行,每行两个整数l, r,表示询问下标i在[l, r]范围内的ai的lcm。
输出格式
  q行。对于每个询问,输出一行,表示对应的答案。
样例输入
3 3
123
234
345
1 2
2 3
1 3
样例输出
9594
26910
1103310
数据规模和约定
测试数据编号
规模和约定
1, 2
n, q<=1000
3, 4
n, q<=5000
5, 6
n, q<=20000
7, 8
n, q<=30000
9, 10
n, q<=40000
11, 12
n, q<=50000
13, 14
n, q<=80000
15, 16
n, q<=100000
17, 18, 19, 20
n, q<=100000 数列a中每个数能表示为不超过100的素数的积
  对于所有测试点,数列a中每个数满足1<=ai<=1000000000。