### PROBLEM LINKS

### DIFFICULTY

Cakewalk

### PREREQUISITES

loops, simple maths

### PROBLEM

Find number of (x, y) pairs such that 1 \leq x \leq H, 1 \leq y \leq W and x * y = K.

### QUICK EXPLANATION

Iterate over x and you can check if there exists a valid y in the desired range satisfying x \cdot y = K or not.

### EXPLANATION

##\mathcal{O}(H * W) bruteforce solution

Constraints on H and W are quite small. We can exploit these to get a

simple bruteforce solution. We iterate over all (x, y) pairs and check

whether their product x * y is equal to K or not. We can count such

valid pairs in \mathcal{O}(W * H) time.

**Pseudo Code:**

```
ans = 0
for x = 1 to H:
for y = 1 to W:
if x * y == K:
ans++
```

##\mathcal{O}(K log K) solution

Let us make a simple change in the last solution? What if we you stop iterating over y when the value

of x * y exceeds K. Will that improve time complexity?

```
ans = 0
for x = 1 to H:
for y = 1 to W:
if x * y > K:
break;
if x * y == K:
ans++
```

Yes, it will. Let us estimate it. From a casual look, it looks that

its time complexity will still be \mathcal{O}(H * W). But it’s not. Let us

delve into depth.

For each x, the inner loop over y will run at most \frac{K}{x} times. So,

total number of iterations the program will be run will be given by

The expression

is also known as harmonic sum H_n. One can prove that H_n = \mathcal{O}(log \, n).

Hence, the time complexity will be \mathcal{O}(K log K).

##\mathcal{O}(H) solution

Let us exploit the condition x * y = K. For a fixed x, do we really need to iterate

over all y's to check how many of them satisfy x * y = K. It turns out, no. Firstly there will be at most a single y. If K is not divisible by x, then there can’t exist such y. Otherwise y will be \frac{K}{x}.

In summary, we iterate over only

x values and find the corresponding y (if it exists), and

check whether the y is \geq 1 and \leq H.

Time complexity of this method will be \mathcal{O}(H), as are iterating over x values only once.

#### Factorization based solutions

If x \cdot y = K, then both x and y should divide K. So we can find all the divisors of the K. Let x be one such divisor, then y will be \frac{K}{x}.

You can find all the divisors of K in \mathcal{O}(sqrt(K)) time.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.