Блог пользователя chubakueno

Summing GCD(i, j) over all 1 ≤ i  <  j ≤ N for N  ≈  235711131719 (TL: 20 seconds)
Автор chubakueno, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить