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?
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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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).
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 × 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.
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 Pn be a set of primes not larger than n.