There is a mysterious organization called GCD. They get a permutation P, permutation is a sequence of length N, only consists of number 1 to N and each number appears only once.
They want to gain magic power from this permutation. For the interval [L, R] they can get power:
∑i=LR∑j=i+1R∑k=j+1R(gcd(P[i],P[j])==P[k])⋅P[k]
Now they have M queries, for each query can you help them calculate how many power they can get？
1850: GCDispower
时间限制: 10 Sec 内存限制: 128 MB提交: 2 解决: 2
[提交][状态][讨论版][命题人:]
题目描述
输入描述
The first line is an integer T which indicates the case number.
And as for each case, first line is two integer N and M which indicates the length of permutation and number of query.
Next line is N integer which indicate the permutation P
Next M line, for each line is two integer L and R which indicate each query.
Limit
1≤T≤100
1≤N,M≤100000
1≤Pi≤N, for any pair (i,j), Pi≠Pj
1≤Li≤Ri≤N
About 95% test case: 1≤N≤1000
Other test case: 1≤N≤100000
And as for each case, first line is two integer N and M which indicates the length of permutation and number of query.
Next line is N integer which indicate the permutation P
Next M line, for each line is two integer L and R which indicate each query.
Limit
1≤T≤100
1≤N,M≤100000
1≤Pi≤N, for any pair (i,j), Pi≠Pj
1≤Li≤Ri≤N
About 95% test case: 1≤N≤1000
Other test case: 1≤N≤100000
输出描述
As for each case, you need to output M integer which indicate the answer of each query.
样例输入
2
3 1
3 2 1
1 3
6 3
6 5 4 3 2 1
1 6
2 6
3 5样例输出
1
8
5
0来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版