Maximum sum of coprime pair

Revision en1, by Enchom, 2016-07-19 13:50:07

Hello everybody,

Today was the practice session of CEOI 2016 and the following interesting problem was given:

You're given N distinct integers. Print the maximum sum you can get by adding two of them that are coprime.

N is up to 100,000 and all the numbers are between 1 and 500,000. Time limit is 1 second, memory limit is 256MB.

Some solutions passed but most of them were using some odd tricks with unclear complexity. I was wondering if some neat solutions exist?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Enchom 2016-07-19 13:50:07 510 Initial revision (published)