All Tracks Data Structures Advanced Data Structures Problem

Not So Simple Function
Tag(s):

Binary Search, Data Structures, Medium-Hard

Problem
Editorial
Analytics

Let us first describe a Complex Function.

Complex Function(vector < int> array) {

    int minimum=1e9;
    for(int a:array){
            minimum=min(minimum,a);
    }
    for(int i=minimum;i>=1;i--){
            bool flag=true;
            for(int a:array){
                    if((a%i)>0)
                        flag=false;
            }
            if(flag==true)
                return i;
    }

}

So the complex function receives a vector and return an integer for that array. Let us call this integer(value returned by the function) as complex value of that array.

Rahul and Sandeep were having coffee this weekend when Sandeep introduced him to this Complex Function. Rahul loved maths. So he got excited on seeing this function. But Sandeep couldn't see Rahul's happiness. So to make his life even worse he asked him an even tougher problem that involved this Complex Function.

Sandeep gave Rahul an array consisting of N integers. He then asked Rahul to compute the complex value of all the subarrays of that array. Something like if Rahul had an array consisting of $$2$$ integers. He asked him to calculate Complex(a[1:1]), Complex(a[2:2]), Complex(a[1:2]). After he did that, Sandeep started shooting queries on Rahul. In each query he gave him two integers L and R and asked him to tell him the total number of subarray such that their complex value lies between L and R (both included).

Rahul had no idea how to solve this problem efficiently. So he turns to you for help. Help Rahul in tackling Sandeep's problem.

Input:

The first line contains N denoting the size of array. This is followed by N space separated integers that denote the elements present in the array. After this line we have an integer Q that indicates the count of queries. Finally we have Q lines, each line containing two integers L and R.

Output:

Output Q lines, each line containing the answer of Sandeep's query.

Constraints:

$$1$$ <= N <= $$10^5$$

$$1$$ <= Array Elements <= $$10^9$$

$$1$$ <= Q <= $$2*10^5$$

$$1$$ <= L <= R <= $$10^9$$

SAMPLE INPUT
3
5 4 2
3
1 2
2 3
1 5
SAMPLE OUTPUT
4
2
6
Explanation

First let us calculate the complex value of all the subarrays. There are 6 subarrays . They are {5}, {4},{2},{5,4},{4,2},{5,4,2}. Their complex values are

Complex({5})=5

Complex({4})=4

Complex({2})=2

Complex({5,4})= 1

Complex({4,2})=2

Complex({5,4,2})=1

So for first query we have subarrays : {5,4,2},{2,4},{5,2},{2}

for second query we have : {2,4},{2}

for final query :- all the subarray satisfy it.

Time Limit: 1.5 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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications