← 返回题目列表

Codeforces · 301/D

D. 雅罗斯拉夫和除数

中文机器翻译题面 查看原题

Yaroslav 有一个数组 p = p1, p2, ..., pn (1 ≤ pi ≤ n),由 n 个不同的整数组成。另外,他还有m个疑问:

- 查询号 i 表示为一对整数 li, ri (1 ≤ li ≤ ri ≤ n)。
- 查询 li, ri 的答案是整数对 q, w (li ≤ q, w ≤ ri) 的数量,使得 pq 是 pw 的除数。

帮助雅罗斯拉夫,回答他所有的疑问。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105)。第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n)。以下 m 行包含 Yaroslav 的查询。第 i 行包含整数 li, ri (1 ≤ li ≤ ri ≤ n)。

输出

打印 m 个整数 — 按照 Yaroslav 查询在输入中出现的顺序给出答案。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

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