×

# 计蒜客

1. 题库
2. query
3. 问答
• 29.45%
• 262144K

Given a permutation \$p\$ of length \$n\$, you are asked to answer \$m\$ queries, each query can be represented as a pair \$(l ,r )\$, you need to find the number of pair\$(i ,j)\$ such that \$l \le i < j \le r\$ and \$\min(p_i,p_j) = \gcd(p_i,p_j )\$.

### Input

There is two integers \$n(1 \le n \le 10^5)\$, \$m(1 \le m \le 10^5)\$ in the first line, denoting the length of \$p\$ and the number of queries.

In the second line, there is a permutation of length \$n\$, denoting the given permutation \$p\$. It is guaranteed that \$p\$ is a permutation of length \$n\$.

For the next \$m\$ lines, each line contains two integer \$l_i\$ and \$r_i(1 \le l_i \le r_i \le n)\$, denoting each query.

### Output

For each query, print a single line containing only one integer which denotes the number of pair\$(i,j)\$.

```3 2
1 2 3
1 3
2 3```

```2
0```

• main.c