number theory - Euler's totient function and related sum

I am supposed to calculate the following sum :
$\sum _{d|n} (n/d) * \phi (n/d)$ where the sum is over all divisors (d) of a given number (n) and $\phi (x)$ is Euler's totient function .

Since the input (n) can be very large ($\leq 10^7$) and the number of test cases are also huge ($\leq 10^6$), hence I am looking for an extremely optimized algorithm.

For this I create a sieve of Eratosthenes setup in which instead of crossing off each multiple, I multiply with $(p-1) \times (n/p)$ where p is a prime factor of the element of array and also , I simultaneously update n/p (dividing each time). So, I create this sieve for $10^7$ elements.

Now, I find the divisors in the usual manner in $O(\sqrt {n})$ complexity. It turns out that this method is slow as the given running time is 1 sec.

Any ideas for further optimization?

Answer

Since you want to compute many values of this multiplicative function, there is an Eratosthenes-inspired way that is (or, I believe, should) be standard.

First, note that $f(n) = \sum_{d\mid n} (n/d)\phi(n/d) = \sum_{d\mid n} d\phi(d)$ is a multiplicative function of $n$; therefore, $f(\prod p^r) = \prod f(p^r)$ for any finite collection of powers $p^r$ of distinct primes. Furthermore, it's easy to check directly that $f(p^r) = (p^{2r+1}+1)/(p+1)$.

So set up an array of $10^7$ values, each initialized to $1$. Then, for every prime power $p^r$, go through and update every $p^r$th element of the array, multiplying its value by $f(p^r)/f(p^{r-1}) = (p^{2r+1}+1)/(p^{2r-1}+1)$. Once you go through all the prime powers less than $10^7$, the values in the array will be the numbers $f(1),\dots,f(10^7)$. The number of multiplications of this type you'll need is quite small, like $10^7 \log\log 10^7$.