[R44F]事事顺 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

定义一个正整数是“顺”的，当且仅当其可以表示为一个正整数的平方与一个质数的乘积。例如：

• $44$ 是“顺”的，因为 $44 = 2^2 \times 11$，其中 $11$ 是质数。
• $12$ 是“顺”的，因为 $12 = 2^2 \times 3$。
• $1$ 不是“顺”的，因为 $1$ 无法表示为 $k^2 \times p$ 的形式（$1$ 不是质数）。
• $8$ 是“顺”的，因为 $8 = 2^2 \times 2$。

给定一个长度为 $n$ 的正整数序列 $a$。现有 $q$ 次询问，每次询问给定一个区间 $[l, r]$，请你求出有多少对整数 $(i, j)$ 满足 $l \le i < j \le r$，且 $a_i \times a_j$ 是“顺”的。

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示序列长度以及询问次数。

第二行包含 $n$ 个正整数，表示序列 $a$。

接下来 $q$ 行，每行包含两个正整数 $l, r$，表示此次询问的区间。

输出格式

对于每次询问，输出一行一个整数，表示满足条件的对数。

样例

样例输入 #1

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

样例输出 #1

3
1
4
6
2

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n, q \le$
$1$	$20$	$1000$
$2$	$80$	$100000$

对于 $100\%$ 的数据，满足 $1 \le n, q \le 10^5$，$1 \le l \le r \le n$，$1 \le a_i \le n$。