因子区间
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Silencer76 定义一个二元组 (a_i,a_j) 是漂亮二元组,当且仅当 i<j 且 a_i 和 a_j 的因子数量相等。
给定一个长度为 n 的正整数序列 a ,以及 q 次询问。
每次询问给出一个区间 [l,r] ,请输出区间中漂亮二元组的数量。

输入描述:

第一行有两个正整数 n\ (\ 1 \leq n \leq 10^5\ ) 和 q\ (\ 1 \leq q \leq 10^5\ )
第二行有 n 个正整数 a_i\ (\ 1 \leq a_i \leq 10^5\ )
随后 q 行,每行两个整数 l,r\ (\ 1 \leq l \leq r \leq n\ )

输出描述:

输出 q 行,每行一个整数,代表漂亮二元组的数量。
示例1

输入

复制
5 5
1 2 3 4 5
1 5
2 3
4 4
2 5
1 4

输出

复制
3
1
0
3
1

说明

1,2,3,4,5 的因子数量分别为 1,2,2,3,2