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

Правка en3, от chubakueno, 2016-03-08 07:21:25

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 time (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)