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.
1 Like
If you switch the positive/negative then it should be fine.
Hi @tmwilliamlin i am waiting for your editorial of Expected Change. Please post that as it has new concept which i am not aware of inverse modulo etc
It has been posted already
@tmwilliamlin Usually editorial link is on problem page. I am not seeing link on problem page CodeChef: Practical coding for everyone . In case you have spare time, kindly share that link with me. Thanks
I am unable to understand explanation 2… Can you please explain it in some easy way so that beginners will understand??? Thanks in advance 
If I find all factors of yk and check for xi and xj pair, will that solution work??
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.
That could (depending on speed of implementation), but I don’t know how to prove its time complexity.
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.
My solution 1 has extra pruning to run in O(factors of y^2 <= 10^5). I’m not sure if you made sure all factors you generated <= 10^5.
Ya,I did not. That’s why its O((n+m)(\sqrt(a_i) +log^2(a_i)))
I factorised a_i, then i kept all the factors in a vector. I paired the factors together, and use an array to store the used factors to prevent recounting before checking in the array, I check whether its lesser than 10^5. At the time I did not know how to use recursion to do that. So afterwards this comes out to be approximately log^2 a_i. The factors are also double counted very often.
Will the factors of y and y^2 ( such that it is <= y ) be same ??
https://www.codechef.com/viewsolution/29545814
Can you please tell me what is wrong in my implementation ??
https://www.codechef.com/viewsolution/29545814
Can you please tell me what is wrong in my implementation?