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

Revision en1, by chubakueno, 2016-03-08 07:17:15

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 need O(N) memory, precalculation 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)