This exploits the fact that if x_1 and -x_2 are the points on the x-axis bracketing the hypotenuse, they must have the same odd-exponent prime factors. This is because y_h = r . x_1 and x_2 = r . y_h, giving x_2 = r^2. x_1 and all changes to prime exponents are even.
So I split each number into x_a = q_a.s_a^2, where s_a is the biggest value possible and q_a is thus square-free, with a sieve of greatest square factors. I store these as pairs (q_i,s_i) for positive and negative x and sort by q. I then only compare x_1, x_2 for a possible y_h (or two, +/-) when they have matching q values, and the value of candidate y_h is directly given by y_h = q.s_1.s_2, looked up in a frequency array as above.
O(N) is the time complexity for a single Y. If you add this up for all Y, you find that this algorithm runs in O(N^2). In the editorial, I prove that it also runs in O(NsqrtN).
This is because of an optimization I made in the dfs function.
if(i>=pf.size()||x*pf[i][0]>mxN)
The second condition x*pf[i][0]>mxN, says that if multiplying by pf[i] is impossible, then assuming that pf is sorted, multiplying by all other pf[j] (j>i) is impossible, so it stops recursing.
I have tried a lot to make sure that beginners can understand. If you say that you canāt understand explanation 2, I donāt really know how to help you. Please at least tell me which part of explanation 2 is confusing for you.
Yes. That is what I did during the contest, but it barely passed the TL(1.99/2 sec), and the implementation is very heavy. https://www.codechef.com/viewsolution/29387562
You need to copy it onto the ide to understand. A lot of lines are broken into 3 lines.
Runs in O(n+m)(\sqrt(a_i) + log^2 a_i)
https://www.codechef.com/viewsolution/30010063
i am facing problems i just cant identify my mistakeā¦
im getting wa for original constraints
im simply using the gaa gbb gab method by using a frequency array
Are you sure it runs in O(n+m)(sqrt(A))? You factor x^2 and y^2, which can take up to sqrt(x^2) and sqrt(y^2) time each (this is if you use the bound of sqrt(n) divisors).
I just read your editorial, I practically did method 1, Just the implementation was different, thatās why the log term came. But thatās what he was asking. But if he wants to factor the square term, you can do it with a sieve in log n maybe, Iām not sure about this.
