主题

主题

 
   

The sum of gcd

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5381

Problem Description

You have an array A,the length of A is n

Let f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

First line has one integers n

Second line has n integers Ai

Third line has one integers Q,the number of questions

Next there are Q lines,each line has two integers l,r

1≤T≤3

1≤n,Q≤104

1≤ai≤109

1≤l<r≤n

Output

For each question,you need to print f(l,r) 

Sample Input

2

5

1 2 3 4 5

3

1 3

2 3

1 4

4

4 2 6 9

3

1 3

2 4

2 3

Sample Output

9

6

16

18

23

10


题目大意:

给出一个长度为n的序列。给出m个询问,每一次询问一个区间,所有子区间的gcd之和。


个人解法:

做此题感觉思路顺理成章……感觉和“HNOI2016序列”一题有些异曲同工之妙。

这道题是2015多校联合#8的。如果HNOI2016之前做到了这道题,考场上此题大概也可以拿很高的分数了吧?

也是一道区间的子区间的题。

我们考虑莫队。

在莫队右端点往右移动的时候,我们考虑如何计算右端点的贡献。

感觉我们需要处理出以当前点为右端点,左边的gcd的情况。具体一点来说,处理出一个数组,记录对于所有的j<i,A[j..i]的gcd。

不过由于我们发现每出现一个新的gcd,都是上一个gcd扣除一个因数得到的。所以gcd的种类是log(w)级别的。我们再记录对应的位置即可计算贡献了。

当然左边的拓展也要处理一个类似的数组。

如何预处理出这个数组?

我们在计算i的这一部分的时候,可以拿i-1的来更新。大致是这样:


每一次转移,我们暴力扫描,计算贡献即可。


代码如下:

https://code.csdn.net/snippets/2307960

 
 
评论