首页 > 试题广场 >

珂朵莉与GCD

[编程题]珂朵莉与GCD

给你一个长为n的序列a

m次查询

每次查询一个区间的所有子区间的gcd的和mod1e9+7的结果


输入描述:
第一行两个数n,m
之后一行n个数表示a
之后m行每行两个数l,r表示查询的区间


输出描述:
对于每个询问，输出一行一个数表示答案
示例1

输入

5 7
30 60 20 20 20
1 1
1 5
2 4
3 4
3 5
2 5
2 3

输出

30
330
160
60
120
240
100

说明

[1,1]的子区间只有[1,1]，其gcd为30
[1,5]的子区间有：
[1,1]=30,[1,2]=30,[1,3]=10,[1,4]=10,[1,5]=10
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共330
[2,4]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20
[3,3]=20,[3,4]=20
[4,4]=20
总共160
[3,4]的子区间有：
[3,3]=20,[3,4]=20
[4,4]=20
总共60
[3,5]的子区间有：
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共120
[2,5]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共240
[2,3]的子区间有：
[2,2]=60,[2,3]=20
[3,3]=20
总共100

备注:
对于100%的数据，有1 <= n , m , ai <= 100000
算法知识视频讲解
开通博客

暂无题解

问题信息

树状数组
上传者：牛客301599号
难度：
0条回答 15浏览

热门推荐

通过挑战的用户

查看代码

相关试题

珂朵莉与GCD

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号