Discussion @ 1807. Cartridges for Maxim @ Timus Online Judge

Give me a hint, I AC this using preprocessing monyura[ONU 1 2/3] 12 Nov 2010 23:45

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 Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 13 Nov 2010 10:43

Optimize

Re: Give me a hint, I AC this using preprocessing SkorKNURE 30 Sep 2011 02:06

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 xurshid_n 17 Jan 2012 19:59

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 luckysundog 11 Feb 2012 17:55

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 xurshid_n 28 Feb 2012 20:28

Edited by author 28.02.2012 20:32

Re: Give me a hint, I AC this using preprocessing xurshid_n 28 Feb 2012 20:29

luckysundog wrote 11 February 2012 17:55

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:19

Re: Give me a hint, I AC this using preprocessing 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?

Discussion of Problem 1807. Cartridges for Maxim