ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1807. Cartridges for Maxim

Give me a hint, I AC this using preprocessing
Posted by 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
Optimize
Re: Give me a hint, I AC this using preprocessing
Posted by 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
Posted by 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
Posted by 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
Posted by 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
Posted by xurshid_n 28 Feb 2012 20:29
luckysundog wrote 11 February 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


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
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?