All Tracks Math Number Theory Problem

Monk and Divisor Conundrum
Tag(s):

Easy, Math

Problem
Editorial
Analytics

Here is another task for you, prepared by Monk himself. So, this is how it goes :

Given an integer array $$A$$ of size $$N$$, Monk needs you to answer $$T$$ queries for him. In each query, he gives you $$2$$ integers $$P$$ and $$Q$$. In response to each of these queries, you need to tell Monk the count of numbers in array $$A$$. that are either divisible by $$P$$, $$Q$$, or both.

Can you cope with this ?

Input Format :

The first line contains a single integer $$N$$ denoting the size of array $$A$$. The next line contains $$N$$ space separated integers, where the $$i^{th}$$ integer denotes $$A[i]$$.

The next line contains a single integer $$T$$ denoting the number of queries Monk poses to you. Each of the next $$T$$ lines contains $$2$$ space separated integers $$P$$ and $$Q$$.

Output Format :

For each query, print the answer on a new line.

Constraints :

$$ 1 \le N \le 2 \times 10^5 $$

$$ 1 \le A[i] \le 2 \times 10^5 $$

$$ 1 \le T \le 2 \times 10^5 $$

$$ 1 \le P, Q \le 2 \times 10^5 $$

SAMPLE INPUT
6
2 3 5 7 4 9
2
4 5
3 7
SAMPLE OUTPUT
2
3
Explanation

For the $$1^{st}$$ query in the $$1^{st}$$ sample, the numbers that form a part of the count are $$4$$ and $$5$$, present at indices $$5$$ and $$3$$ respectively.

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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Number Theory Part I)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications