deepkamal's blog

help in a problem TRENDGCD at spoj
By deepkamal, history, 4 years ago, In English

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/

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it +3 Vote: I do not like it

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:

$$$ \begin{aligned} \sum_{i=1}^a\sum_{j=1}^b i\cdot j\cdot f(\gcd(i,j)) &= \sum_{i=1}^a\sum_{j=1}^b i\cdot j\cdot \sum_{d|\gcd(i,j)} g(d)\\ &= \sum_{i=1}^a\sum_{j=1}^b i\cdot j\cdot \sum_{d|i,d|j} g(d)\\ &= \sum_{d=1}^{\min(a,b)} g(d)\sum_{i=1}^{\lfloor{a/d}\rfloor}\sum_{j=1}^{\lfloor{b/d}\rfloor} (i\cdot d)(j\cdot d)\\ &= \sum_{d=1}^{\min(a,b)} g(d)(\sum_{i=1}^{\lfloor{a/d}\rfloor}(i\cdot d))(\sum_{j=1}^{\lfloor{b/d}\rfloor} (j\cdot d))\\ &= \sum_{d=1}^{\min(a,b)} g(d)d^2(\sum_{i=1}^{\lfloor{a/d}\rfloor}i)(\sum_{j=1}^{\lfloor{b/d}\rfloor} j)\\ \end{aligned} $$$

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$$$.

→ Reply