|
|
back to boardHow do you solve this problem ? Posted by rohit 25 Sep 2011 01:12 Some hints please. My algo takes too much time. Re: How do you solve this problem ? You need factoring N by numbers 2..10^6. If after factoring N>1 and N not prime, then your N=p*q, where p and q - prime numbers. Edited by author 27.09.2011 16:46 Re: How do you solve this problem ? Posted by svr 10 Oct 2011 14:33 most difficult case n=p*p, where p- is prime for it case quick _int64 sqrt(__int64 n) function is needed, in other cases there is a factor of n which is <1000000. Re: How do you solve this problem ? svr what should be the output when n = p*p where p is prime ?? i guess just n ? becuase n is already odd and its the maximum ? Edited by author 19.01.2015 01:04 Re: How do you solve this problem ? I just did straight forward factorization (with rho) of an input number and then divided it by primes that have an odd power in factorization. 0.31 ms, 1400 kb. Edited by author 08.07.2018 18:21 Re: How do you solve this problem ? AC in 0.015 (in plain C) with something much simpler than RHO. - start factorizing the simplest way they teach you in the kindergarten - when the test reach large values, check if the reminder has a perfect square -- if so - return the square and count as it is a prime divisor ^2 (because even if it can be factorized, it will be an amount of multipliers ^2) -- if no - stop checking (because the reminders are obviously large prime values ^1 and can be ignored) - multiply all primes with even powers * primers with odd powers (n) >= 3 with power n-1 I bet it can be accepted in 0.001 if Intel C 7 was still a compiler option. |
|
|