### PROBLEM LINK:

**Author:** Aniket Marlapalle

**Tester:** Harsh Shah

**Editorialist:** Aniket Marlapalle

### DIFFICULTY:

easy-medium

### PREREQUISITES:

maths number-theory

### PROBLEM:

Given an array of numbers and Q queries to process. In each query given an integer **K** find how many pairs (i and j) exist in the array such that the product **A _{i} and A_{j}** divides

**K**.

### EXPLANATION:

The values of **A _{i} and K** are limited to 10

^{6}so lets do some pre-processing and answer the queries in

**O(1)**

**Step 1**:

Let’s solve a relatively easier problem of finding the pairs such that their product equals some value **X**.First we will store the counts of all the numbers in a separate array. Then let’s pick an element one by one and iterate over all its multiples, lets say the current element is **i** and it’s multiple that we are considering is **Y** then the number of pairs such that their product equals to **Y** and one of these numbers being **i** is **count[i]*count[Y/i]** we add this value to the ans. Thus for every number **i** we iterate over **max(A)/i** numbers. This takes a time of **O(max(A)*log(max(A)))**. This gives us ordered pairs but we want unordered so we have to divide this number by 2.

**Step 2**:

Now we have the count of pairs with product equal to i stored in **ans[i]**. Now let’s solve the given problem, we need to find the total pairs such that their product divides **K** we can rephrase this problem as K is a multiple of their product. So like in previous step we again iterate over all the values and their multiples too and create a global answer array by adding the **ans[i]** to **global[Y]** where **Y** is a multiple of **i**.

Now we can answer every query in **O(1)** by just printing **global[K]**.

Total Complexity : **O(max(A)*log(max(A)))** where max(A) is maximum value in the given array which is (10^{6}).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here