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

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский chubakueno 2016-03-08 07:27:06 14
en4 Английский chubakueno 2016-03-08 07:25:39 24 Tiny change: 'lgorithms need $O(N' -> 'lgorithms in the original article need $O(N'
en3 Английский chubakueno 2016-03-08 07:21:25 28 Tiny change: 'lculation (to answe' -> 'lculation time (to answe'
en2 Английский chubakueno 2016-03-08 07:19:45 34 (published)
en1 Английский chubakueno 2016-03-08 07:17:15 523 Initial revision (saved to drafts)