chubakueno's blog

Summing GCD(i, j) over all 1 ≤ i  <  j ≤ N for N  ≈  235711131719 (TL: 20 seconds)
By chubakueno, history, 9 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What have you tried other than directly applying algorithms from the original article?

It might be obvious, but is good enough. You just have to get rid of that precomputation somehow.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The final problem lies in computing prefix sums of f(n) = φ(n) fast enough without precalculation, but i don't have a clear idea on how to deal with that problem.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +33 Vote: I do not like it

      The sum is, remembering the definition of the totient, the number of pairs (a, b) such that a <= b <= n and gcd(a, b)=1.

      Let's call the sum of all pairs a <= b <= n such that gcd(a, b) = g the function S(n, g).

      Clearly every pair has exactly one gcd, so the sum of all S is the total number of pairs: , or .

      This is a little tricky, but as gcd(a, b) = g if and only if gcd(a/g, b/g) = 1, you can write S(n, i) = S(n/i, 1),giving the equation .

      This should allow you to get those prefix sums in time.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Actually, being able to compute S (N, K) the answer may be rewritten as: sum of i * S (N, i) for i = 1, N which is also sum of i * S (N / i, 1). And, as in the article, N / i can take up to sqrt (N) values, so we'll have to compute just sum of the j which have [N / j] the same (these js will form a subsequence).

        LE: I've just got AC with this solution

        → Reply