Preparing NOJ

GCDispower

5000ms 65536K

Description:

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:
$$$\sum\limits_{i=L}^R\sum\limits_{j=i+1}^R\sum\limits_{k=j+1}^R (gcd(P[i], P[j]) == P[k]) \cdot P[k]$$$
Now they have M queries, for each query can you help them calculate how many power they can get´╝č

Input:

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 \leq T \leq 100$$$
$$$1 \leq N, M \leq100000$$$
$$$1 \leq Pi \leq N$$$, for any pair $$$(i, j)$$$, $$$Pi \neq Pj$$$
$$$1 \leq Li \leq Ri \leq N$$$

About 95% test case: $$$1 \leq N \leq 1000$$$
Other test case: $$$1 \leq N \leq 100000$$$

Output:

As for each case, you need to output M integer which indicate the answer of each query.

Sample Input:

2
3 1
3 2 1
1 3
6 3
6 5 4 3 2 1
1 6
2 6
3 5

Sample Output:

1
8
5
0

Info

HDU

Provider HDU

Origin 2017 Multi-University Training Contest - Team 6

Code HDU6102

Tags

Submitted 9

Passed 5

AC Rate 55.56%

Date 06/03/2019 16:55:32

Related

Nothing Yet