All Tracks Data Structures Advanced Data Structures Segment Trees Problem

The Market
Tag(s):

Data Structures, Dynamic Programming, Medium, Segment Trees, Sieve, approved

Problem
Editorial
Analytics

There are N items in a market (indexed from 1 to N) each having a particular cost. The danger value of each item is given by the following pseudo code:

           Danger(cost) {
              danger_val = 0
              for ( each i from 1 to cost) {
                   if( cost modulo i is 0  ) {
                       increase danger_val by 1
                   }
              }
              return danger_val
          }

You are given Q queries which contain a range of items.

You need to find the number of pairs of items that have the same danger value.

Input format

  • First line of the input contains a single integer N
  • Second line of the input contains N space-separated integers denoting the prices of the items.
  • Third line of the input contains a single integer Q denoting the number of queries
  • Each of the next Q lines contain two space-separated integers L and R denoting the range of the items.

Output format

For each query, print the number of pairs of items that have the same danger value.

Constraints

  • \(1 ≤ N,Q ≤ 10^{5}\)
  • \(1 ≤ L ≤ R ≤ N\)
  • \(1 ≤ cost\ of\ item ≤ 10^{6}\)

SAMPLE INPUT
4
2 4 5 8
4
1 3
2 4
1 4
4 4
SAMPLE OUTPUT
1
0
1
0
Explanation

Danger values are \([2, 3 , 2 , 4]\) for the given sample input.
Pairs having same danger value for :
Query 1. 1st and 3rd item.
Query 2. No pair
Query 3. 1st and 3rd item.
Query 4. No pair

Time Limit: 1.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:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?