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?

# | User | Rating |
---|---|---|

1 | tourist | 3686 |

2 | LHiC | 3336 |

3 | wxhtxdy | 3329 |

4 | Benq | 3311 |

5 | Um_nik | 3301 |

6 | V--o_o--V | 3275 |

7 | Radewoosh | 3268 |

8 | yutaka1999 | 3190 |

9 | ainta | 3180 |

10 | Petr | 3115 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | Radewoosh | 184 |

3 | rng_58 | 165 |

4 | PikMike | 164 |

5 | Vovuh | 159 |

6 | majk | 153 |

6 | 300iq | 153 |

8 | Um_nik | 148 |

8 | Petr | 148 |

10 | neal | 144 |

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?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2019 02:44:08 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Because 2

^{w(i)}≤d(i) (d(n) is the number of divisors ofn), 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).At the first look I was totally surprised about this fact, but it sounds easy when you say it like that!

Thanks!

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

It's one of training tasks for our national OI (INOI):

Consider a

n×nforest. 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≤ 10^{6},distance((a,b), (c,d)) = |a-c| + |b-d|Also you can use that fact for this problem.

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

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

What about lower bound? I can prove just Ω(

nloglogn)Lower bound:

Let

P_{n}be a set of primes not larger thann.(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 2

^{x}is convex we get that it's at least .