|
|
back to boardGive me a hint, I AC this using preprocessing I use Dynamics that originally need 31607*3400 operation for input 31607*31607, but when I notice that only first 114 prime numbers uses, and only first 8 of them with power more than 1, I reduce operation count to 200*31607. BTW it works smth about 3 sec. So I use preprocessing to solve it. Does exist another algorithm, or I need to optimize this one? (I think people, who ac this problem, guess algorithm by it complexity) Re: Give me a hint, I AC this using preprocessing Optimize Re: Give me a hint, I AC this using preprocessing Maybe that can help someone to solve... /* * Firstly note that according to the problem statement N is composite. * Then find smallest divisor M that N%M == 0 and let G = M/N. * Now we can factorize N as N = G*M = G*(a1 + a2 + ...) and consider * values G*a[i], gcd(G*a1, G*a2, ...) == G as the answer. Those values * will have the largest GCD. It can be easily proved that to maximize * LCM all a[i] must be coprime and be of the form prime^k. * Use dp to find such partition... */ Re: Give me a hint, I AC this using preprocessing But when N~ 10^9 and N - is prime number, than smalles divisor M = N, and G = N/M = 1. a[1] + a[2] + ...a[k] = M ~10^9 . how do use DP? Re: Give me a hint, I AC this using preprocessing N cannot be a prime number, it's always composite. Read the statement carefully > each box contained at least one hundred cartridges. > Anka noticed that there was the same number of cartridges in all boxes maybe it will be more correct to replace "in all boxes" with "in each box"? Edited by author 11.02.2012 17:56 Re: Give me a hint, I AC this using preprocessing Edited by author 28.02.2012 20:32 Re: Give me a hint, I AC this using preprocessing N cannot be a prime number, it's always composite. Read the statement carefully > each box contained at least one hundred cartridges. > Anka noticed that there was the same number of cartridges in all boxes maybe it will be more correct to replace "in all boxes" with "in each box"? Edited by author 11.02.2012 17:56 Thank you!!!!!!!!!! Hovewer, if M - is smalles divisor of N, than 1 < M < 31623 ! I Ac, with 0.046 s !! Edited by author 28.02.2012 22:19 Edited by author 28.02.2012 22:19Re: Give me a hint, I AC this using preprocessing Posted by neko13 7 Aug 2013 22:25 Could you give me some hints about how to breakup a prime as m=a1+a2+a3... so that lcm(a1,a2,a3,...) is biggest? |
|
|