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)

Optimize

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...
 */

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?

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

Edited by author 28.02.2012 20:32

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

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?