# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Sonu Kumar Deo

Tester: Felipe Mota, Abhinav Sharma

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2535

# PREREQUISITES:

Coordinate Geometry

# PROBLEM:

While playing in the plains, Chef found a point A with coordinates (X, Y).

Chef is interested in finding the number of straight lines passing through the point A such that their intercepts on both axes are **positive integers**.

# EXPLANATION:

We can see that the required equation of line can be written as

This can be further written as:

Taking P = (a-x), Q = (b-x) and N = xy, we get

Now we just need to find different values of P and Q such that it satisfies the above equality, which can also be viewed as different number of ways as N can be written as a product of two numbers.

To solve this we would do prime factorisation of N. This can be done using sieve or just iterating till square root of x and y.

Finally N can be written as

where p_1, p_2.....p_k are prime factors of N. Now we would form our number P from p_1, p_2.....p_k and Q would simply be \frac{N}{P}, Now to form P, for each i, we can either take p_i^0 or p_i or $p_i^2$orâ€¦p_i^{r_i}. Thus for each i we would have r_i + 1 options to choose from. Thus our final answer would be the same as number of ways to form P which can be written as:

# TIME COMPLEXITY:

O(\sqrt{x} + \sqrt{y})

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution