I, as a ACMer, always take algorithm complexity into consideration when programming. Today, I introduce you some elegant algorithms of root Complex.

1. $s(n) = \sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$

Since The range of $\lfloor \frac{n}{i} \rfloor$ contains at most $2\sqrt{n}$ . There may exist a algorithm of complexity $O(\sqrt{n})$.

Actually, $s(n)$ donate the number of positive integer point under graph $xy=1$.

2. $\sigma_k(n) = \sum_{d|n} d^k$

1. $\sigma_0(n)$ donate the number of divisors.
2. $\sigma_1(n)$ donate the sum of divisors.

The code above is primary and trival.

3. $f(n) = \sum_{i=1}^n \sigma_k(i)$

$$f(n) = \sum_{i=1}^n \sigma_k(n) = \sum_{i=1}^n \sum_{d|i} d^k = \sum_{d=1} d^k \sum_i ^n[d|i] = \sum_{d=1} ^n d^k \lfloor \frac{n}{d} \rfloor$$

If we get $ts[n] = \sum_{i=1}^n i^k$, similar to problem 1, we have fllowing C++ code:

Actuall, we have
$$ts[n] = \left \{ \begin{array}{ll} \frac{n(n+1)}{2} & k=1 \\ \frac{n(n+1)(2n+1)}{6} & k=2 \\ \frac{n^2(n+1)^2}{4} & k=3 \\ \end{array} \right.$$
and for general

$$1^p+2^p+ \dots + n^p = \sum _{k=1} ^p \; (\; \sum_{j=1} ^ {k} (-1)^{k-j} C_k^j j^p \;) \; C _{n+1} ^{k+1}$$

you can see my blog for detail.

4. $g(n) = \sum_{i=1}^n\phi(i)$

Throughout this blog, $\phi(n)$ donate the Euler function unless explicitly stated.$\phi(n)$ counts the positive integers less than or equal to n that are relatively prime to n. Euler’s product formula:
$$\phi(n) = n \prod _{p|n}( 1-\frac{1}{p} )$$
where the product is over the distinct prime numbers dividing n.

Now, we begin to computer $g(n)$
$$g(n) = \sum_ {i=1}^n \phi(i) = \sum_{1 \leq x \leq y \leq n , gcd(x,y)=1} 1$$

we define
$$g_k(n) = \sum_ {i=1}^n \phi(i) = \sum_{1 \leq x \leq y \leq n , gcd(x,y)=k} 1 = f(\lfloor \frac{n}{k} \rfloor)$$

and $\sum_{i=1}^n g_k(i) = \sum_{1 \leq x \leq y \leq n} 1 = \frac{n(n+1)}{2}$ So we have

$$g(n) = \frac{n(n+1)}{2} - \sum_ {k=2}^n f(\lfloor \frac{n}{k} \rfloor)$$

Similar to problem 1,we have,

5. Problem hdu5608

If
$$n^2 -3n+2 = \sum_ {d|n} f(d)$$
calculate
$$h(n) = \sum_{i=1}^n f(i) \; mod \; 10^9+7$$

Since
$$\sum_{i=1}^n \sum_ {d|i} f(d) = \sum_{i=1}^n f(i) \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^n h(\lfloor \frac{n}{i} \rfloor)$$
and we have,

$$\sum_{i=1}^n \sum_ {d|i} f(d) = \sum_{i=1}^n n^2-3n+2 = \sum_{i=1}^n (n-1)(n-2) = \frac{n(n-1)(n-2)}{3}$$

by conditon. Hence,
$$h(n) = \frac{n(n-1)(n-2)}{3} - \sum_{i=2}^n h(\lfloor \frac{n}{i} \rfloor)$$

6. Note

All C++ code above should be changed to fit different demands.Thanks Zimpha who provides some problems and ideas two years old.