Yaroslav and Divisors

题意翻译

### 题意： + 给定一个由$n$个数组成的排列，每个数互不相同且数字不会超过$n$，你需要回答$m$个询问。 + 询问包含两个整数$l$和$r$$(1<=l,r<=n)$。 + 对于每个询问，查询有多少数对$i,j(l<=i,j<=r)$。使得$pi$与$pj$是倍数关系。 ### 输入格式： + 第一行输入两个数n,m$(1<=n,m<=2*10^{5})$,表示序列长度和询问个数 + 第$2$行输入$n$个数代表这个排列。 + 接下来输入$m$个数对$l, r$代表每一次询问 ### 输出格式： + 输出一个整数代表答案 ### hint： + 建议阅读样例加深理解

题目描述

Yaroslav has an array $ p=p_{1},p_{2},...,p_{n} $ $ (1<=p_{i}<=n) $ , consisting of $ n $ distinct integers. Also, he has $ m $ queries: - Query number $ i $ is represented as a pair of integers $ l_{i} $ , $ r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ . - The answer to the query $ l_{i},r_{i} $ is the number of pairs of integers $ q $ , $ w $ $ (l_{i}<=q,w<=r_{i}) $ such that $ p_{q} $ is the divisor of $ p_{w} $ . Help Yaroslav, answer all his queries.

输入输出格式

输入格式

The first line contains the integers $ n $ and $ m $ $ (1<=n,m<=2·10^{5}) $ . The second line contains $ n $ distinct integers $ p_{1},p_{2},...,p_{n} $ $ (1<=p_{i}<=n) $ . The following $ m $ lines contain Yaroslav's queries. The $ i $ -th line contains integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ .

输出格式

Print $ m $ integers — the answers to Yaroslav's queries in the order they appear in the input. Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

1 1
1
1 1

输出样例 #1

1

输入样例 #2

10 9
1 2 3 4 5 6 7 8 9 10
1 10
2 9
3 8
4 7
5 6
2 2
9 10
5 10
4 10

输出样例 #2

27
14
8
4
2
1
2
7
9