Can anyone tell me whats wrong in my code? I got WA for the last 2 subtasks.
http://www.codechef.com/viewsolution/4911280
My solution is as follows: Find the maximum power in the factorization of each number of every prime number. Now add all these max. powers. The function pow2(int,int) is used to calculate the maximum power of prime p that can divide a given number. The array p1[] is used to store the maximum power for all primes in the array p[].
Can someone please tell me why my solution is giving WA for subtask 3? My code CodeChef: Practical coding for everyone
can we solve it by findind d lcm and den calulating total prime factors, which approach can solve it in better runtime. plz help
Yes i also tried the problem by finding the lcm of all the numbers and then calculated the no. of prime factors of the lcm of all the numbers… but it gives WA … how it is wrong can anybody explain…plz ??
Hi,
I have used the same approach as described in the solution, and getting correct answer for the first task. But I am getting incorrect answer for 2nd and 3rd tasks. Could someone take a look as to what would have went wrong in my approach? I have generated lot of random testcases for the 2nd task and compared solution in editorial to my solution and am getting the same answer for all the tests. I really request someone to please take a look and let me know.
http://www.codechef.com/viewsolution/4945527
Thanks
The following link is my code:
http://www.codechef.com/viewsolution/5480907
It’s resulting in a TLE for the last subtask. Could someone please suggest some ways to optimize this to get it accepted within the time limit? I have exactly followed the method described in the editorial, so it is my factorization technique (brute force sieve method as mentioned in editorial only 
) which is far too long I guess.
Or is trial division redundant in this problem and I have to resort to Pollard Rho method?
You only need to find out primes till 10^3 your sieve finds upto 10^6
@anta0 has found primes till 10^6 too - CodeChef: Practical coding for everyone
Also, why should finding primes till 10^6 TLE?
The complexity of the SOE is O(n(logn)(loglogn)) and that gives ~ 8*10^7 for n = 10^6 which is most probably too high here.
@thezodiac1994 with the right implementation you can get 10^6 seive run cause O(n(logn)(loglogn)) for 10^6 given 5e6 not 8e7
yep same mistake I was doing, finding primes upto 10^6.
The number <= 10^6 itself can be a prime.
Yeah. Lol. Didn’t even think of that!
@chalubhalu there are 78000 primes below 10^6 checking all of them for each iteration of n will give complexity 7.8*10^9. @wittyceaser @anta0 's sieve finds prime factors till 10^3 only. Finding Primes does not take much time checking the divisibility of them with each number does.
also complexity of SOE is nloglogn
@chalubhalu - An iteration test on the standard implementation gave roughly 4e6. The O notation gives 8e7 and that is correct because it is supposed to be the O notation and not Θ notation.
@wittyceaser - 4e6 shouldnt be a problem. So what might be the problem is that you are running the main loop for all the primes in the 10^6 mark. Since there are ~ 8e4 primes and you are checking each prime with each element, given Nmax=10^5 in the first and third sub tasks, your respective calculations become 8e9 - which is surely high.
The second one has Nmax=10 and hence the AC I believe.
For each element there will be log N operations at max since we are dividing with primes at each step. Hence, sieve() is performed in NloglogN, And approximately N*log(10^6) in worst case, which would be well under the limit. A couple of small changes gave me AC, with the same method.
What I want to point out is that never will we be multiplying all 8e4 primes, as the limit on a[i] is 10^6.
Even I cauclated primes till 10^6 using sieve but I got 50 points. http://www.codechef.com/viewplaintext/4919500
@wittyceaser
The point of log N factors is apt. However consider this - if all elements are primes in range ~ 10^6 (repetitions allowed)- then your loop was checking for all prime factors up to the number i.e ~ 8e4 factors would have been checked for each element in the worst case and N*8e4 has to time out regardless of log N factors - unless of course you modify the things.