In order to solve it we must have an efficient method of calculating prime factors of big numbers. Brent factorization is helpful here. The problem is actually about counting divisors for numbers of the form: s * p1^k1 * p2^k2 where GCD(s, p1) = 1 and GCD(s, p2) = 1. Caching is also necessary as we count divisors for the same numbers many times.

I don't see how there could be multiple solutions (a,b,p) for different alpha's. 1/a+1/b is unique and p/(p1^alpha1*p2^alpha2) is also unique.

Why is the editorial available only after solving the problem? If anyone solves the problem why he would even look at the editorial. And even testcases aren't availavle :-(

hi there, I just want to ask is p must b prime number?

Hi,

great task. Thanks. I have two questions:

1.) you write, the "tuple" {a, b, p} has to be counted, but mathematically you write it as a set. How do I have to count then? Like it's a set, or like its a tuple?

For example if I have a solution:

a=2, b=5, p=7

then of course also

a=5, b=2, p=7 would be a solution, but the latter is not countet, because of the constraint a<=b, but what if I also have a solution

a=2, a=7, p=5

with the same alpha-values? Would I have to count these three as 1 solution (like if it's a set, or as two, like it is a tuple)?

If you mean they have to be counted as two distinct solutions you could consider restating the question as:

Count the number of distinct tuples with (a, b, p, alpha1, alpha2) where a<=b.

That would maybe be clearer and shorter.

2.) and related, p has to be a prime, right?

Thank you in advance Jürgen