Coprime-twin pairs
Tag(s):

## Advanced Algorithms, Algorithms, Medium-Hard, Square Root Decomposition

Problem
Editorial
Analytics

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$

SAMPLE INPUT
6 6
2 4 6 8 6 4
3 5
2 4
1 4
1 5
2 5
1 6

SAMPLE OUTPUT
0
1
6
10
2
19

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in Challenge Name

December Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Algorithms > Dynamic Programming
• Basic Programming > Implementation
• Data Structures > Trees
Notifications

?