Блог пользователя M.Mahdi

Why it's O(nlogn)?
Автор M.Mahdi, 10 лет назад, По-английски

Hi!
Did you know is O(nlogn)? (ω(n) is the number of distinct prime divisors of n)

I wonder why! Do you have any mathematical proof for this?

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

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +336 Проголосовать: не нравится

Because 2w(i) ≤ d(i) (d(n) is the number of divisors of n), so this is less than sum of d(i), which is the number of pairs i, j such that j divides i, which is sum of n/j, which is O(nlogn).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +100 Проголосовать: не нравится

    At the first look I was totally surprised about this fact, but it sounds easy when you say it like that!
    Thanks!

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      it's nice information, do you know any problems that can be solved using it?

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

        It's one of training tasks for our national OI (INOI):
        Consider a n × n forest. For each relatively prime pair (i, j)i, j ≤ n, we plant a tree on position (i, j). The problem is to calculate total sum of pairwise distances between trees!
        n ≤ 106, distance((a, b), (c, d)) = |a - c| + |b - d|

        Also you can use that fact for this problem.

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          I don't think that much theoretically about problem, since each number lower than 10^6 has at most 7 distinct prime divisor, we can perform 2^7 * 10^6 :D This problem is much like SGU 370

          → Ответить
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +24 Проголосовать: не нравится

            Yes, but it's always good to know the exact complexity of our solution! (Without considering the limits)

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

What about lower bound? I can prove just Ω(nloglogn)

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

Lower bound:

Let Pn be a set of primes not larger than n.

(look here: http://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes). It follows that average number of different primes divisors is , so since 2x is convex we get that it's at least .

→ Ответить