I have been trying to solve this problem for a while now but made no progress. Can anybody help with TRENDGCD — Trending GCD at spoj.it is related to mobius function. here is link to the problem https://www.spoj.com/problems/TRENDGCD/
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
I have been trying to solve this problem for a while now but made no progress. Can anybody help with TRENDGCD — Trending GCD at spoj.it is related to mobius function. here is link to the problem https://www.spoj.com/problems/TRENDGCD/
Название |
---|
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Let $$$g(d)$$$ be the function such that $$$f(n) = \sum_{d|n} g(d)$$$.
Since $$$f(1) = 1$$$, this is guaranteed to exist. With some number theoretic knowledge, we know that $$$g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$$$
Calculating the Dirichlet convolution of two functions up to $$$n$$$ takes $$$O(n\log(n))$$$ time and pre-computing the $$$\mu$$$ function takes $$$O(n)$$$ time using linear sieve. Hence we can get $$$g(n)$$$ in $$$O(n\log(n))$$$ time.
Now we rewrite the thing to be calculated:
Now it's solvable in $$$O(n)$$$ time per case.
Note that when $$$n$$$ is fixed, $$$\lfloor{n/d}\rfloor$$$ only takes up to $$$2\sqrt{n}$$$ distinct values and is non-increasing as $$$d$$$ grows. Therefore, if you pre-calculate the prefix sum of $$$g(d)d^2$$$, you will be able to calculate the contribution for each segment in $$$O(1)$$$ time. This results in a $$$O(\sqrt{n})$$$ solution.
Here is my code
P.S.: Given $$$d\le n$$$, the largest number $$$r$$$ such that $$$ \lfloor{n/d}\rfloor = \lfloor{n/r}\rfloor$$$ is $$$r = \lfloor{n/(\lfloor{n/d}\rfloor)}\rfloor$$$.
thank you so much