Summing GCD(i, j) over all 1 ≤ i  <  j ≤ N for N  ≈  2  *  1011 (TL: 20 seconds)

Revision en4, by chubakueno, 2016-03-08 07:25:39

After reading a very interesting article about Mobius function , I stumbled into one of the proposed problems, GCDEX2 . The problem is, all the proposed algorithms in the original article need O(N) memory, precalculation time (to answer queries in time ), which is too much for the proposed constraint. Ideas? Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English chubakueno 2016-03-08 07:27:06 14
en4 English chubakueno 2016-03-08 07:25:39 24 Tiny change: 'lgorithms need $O(N' -> 'lgorithms in the original article need $O(N'
en3 English chubakueno 2016-03-08 07:21:25 28 Tiny change: 'lculation (to answe' -> 'lculation time (to answe'
en2 English chubakueno 2016-03-08 07:19:45 34 (published)
en1 English chubakueno 2016-03-08 07:17:15 523 Initial revision (saved to drafts)