CUCRLINE Editorial

editorial
, , , ,
1

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

\frac{x}{a} + \frac{y}{b} = 1

This can be further written as:

(a-x)(b-y) = xy

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

PQ = N

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

N = p_1^{r_1} \times p_2^{r_2} \times.......p_k^{r_k}

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:

answer = \prod_{i=1}^{i=k} (r_i + 1)

TIME COMPLEXITY:

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

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

3 Likes
2

It is giving TLE on half of the test cases, can anyone help me on how to optimize it

X,Y = [int(x) for x in input().split()]
d = {}
for _ in range(2,X+1):
while(X%==0):
X /= _
if _ in d.keys():
d[] += 1
else:
d[_]=1

for _ in range(2,Y+1):
while(Y%==0):
Y /= _
# print()
# counter += 1
if _ in d.keys():
d[] += 1
else:
d[]=1

ans = 1
for _ in d.values():
ans *=(_+1)
print(ans)