← 返回题目

题库练习 Yaroslav and Divisors

← 上一题下一题 →

A9040 | $Yaroslav and Divisors$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #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

C++ 编辑器

输入

输出