All Tracks Algorithms Problem

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), TypeScript, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?