SOLVE

LATER

Coprime-twin pairs

/

A pair of distinct positive integers \((a, b)\) is said to be a coprime-twin pair, if for all positive integers \(x\), both \(a\) and \(b\) are coprime to \(x\) or both \(a\) and \(b\) are not coprime to \(x\). Formally, 2 distinct positive integers \(a\) and \(b\) can form a coprime-twin pair if and only if \(S(a) = S(b)\), where \(S(x)\) denotes the set of all positive integers that are coprime to \(x\). For example,

- \((2, 4)\) and \((18, 24)\) are coprime-twin pairs.
- \((1, 2)\) and \((4,6)\) are not coprime-twin pairs.
- \((3, 3)\) is not a coprime-twin pair because a coprime-twin pair must consist of distinct integers.

The score of a sequence \(a_1, a_2, ..., a_n\) is the number of indices \(i, j\) such that \(1 \le i < j \le n\) and the pair \((a_i, a_j)\) forms a coprime-twin pair.

You are given an array \(A\) of \(N\) positive integers and \(Q\) queries of the form \(L, R\). For each query, determine the sum of the scores of all subarrays that completely lie within the range \([L, R]\) (both inclusive).

*Note*: A subarray is a contiguous non-empty segment of the array. If a subarray completely lies within the range \([L, R]\), then it means that both its endpoints lie within this range.

**Input format**

- First line: Two space-separated integers \(N\) and \(Q\) where \(N\) denotes the size of the array \(A\) and \(Q\) denotes the number of queries respectively
- Next line: \(N\) space-separated integers that represent the array \(A\)
- Next \(Q\) lines: Two space-separated integers \(L \ R\)

**Output format**

For each query, print the answer to the query in a new line as mentioned in the problem statement.

**Constraints**

\(1 \le N, Q \le 10^5\)

\(1 \le A_i \le 10^6\)

\(1 \le L \le R \le N\)

Explanation

For the first query, there are no coprime-twin pairs in this range.

For the second query, \([2, 4]\) is the only subarray having score 1 (because of the coprime-twin pair \((4, 8)\) ). All other subarrays have score 0.

For the third query, the subarrays and their scores are :

\([1, 1], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4] \ \ \ => \ \ \ score = 0\)

\([1, 2], [1, 3], [2, 4] \ \ \ => \ \ \ score = 1\)

\([1, 4] \ \ \ => \ \ \ score = 3\)

The sum of the scores is therefore, \(6\).

The answers to the remaining queries can be found similarly.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...