I've seen a few other threads on here, namely this and this, which mention and discuss the Divisor Summatory Function $D(x)=\sum_{n=1}^x\sigma_0(n)$ for parameters other than $x$. But neither quite fit what I'm looking for: in the first link (and the wikipedia page for $D(x)$), it is noted that $$D(x)=\sum_{k=1}^x\bigg\lfloor\frac{x}{k}\bigg\rfloor=2\sum_{k=1}^u\bigg\lfloor\frac{x}{k}\bigg\rfloor-u^2, u=\lfloor\sqrt x\rfloor$$ Which can compute $D(x)$ in $\mathcal{O}(\sqrt x)$ time. Now suppose I define $D'(x) = \sum_{n=1}^x\sigma_0(kn)$ for some integer $k$. I need to compute this for different values of $k$ in far faster than $\mathcal{O}(x)$ time, but I don't think that formula applies any longer and I can't seem to find or derive anything similar. Any ideas?
EDIT 1: At this rate, I've started moving on from that above expression in favor of fiddling around with the prime powers. If $k$ and $n$ are relatively prime, then clearly $\sigma_0(kn)=\sigma_0(k)\sigma_0(n)$. Suppose $n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$. I've noticed that if $k=p_i$ is prime, \begin{equation} \begin{split} \sigma_0(kn) & = (a_1+1)(a_2+1)...((a_i+1)+1)...(a_n+1) \\ & = (a_1+1)...(a_{i-1}+1)(a_{i+1}+1)...(a_n+1)+\sigma_0(n) \\ & = \frac{\sigma_0(n)}{p_i^{a_i}}+\sigma_0(n) \\ & = \frac{p_i^{a_i}+1}{p_i^{a_i}}\sigma_0(n) \end{split} \end{equation}
Similarly, if $k=p_i^q$ is a prime power then $\sigma_0(kn)=(p_i^{a_i}+q)p_i^{-a_i}\sigma_0(n)$. The only case I have not put in some terms of $\sigma_0(n)$ are composite factors of $x$, which for $x$ which aren't absolutely enormous are computable in negligible time. All that's needed now is to somehow simplify to lower the number of terms necessary, probably by combining certain cases when $k$ relatively prime to $x$ and/or a prime power somehow. It is here I once again hit a wall.
Let us use $\tau(n):=\sigma_0(n)$. For given $k$, the function $n\mapsto \tau(kn)$ is not multiplicative in general. But, if it is possible to write down Dirichlet series of this function, then it will give us a useful formula for $\sum_{n\leq x} \tau(kn)$. i.e. We aim for finding $F(s)$ in the expression: $$ \sum_{n=1}^{\infty} \frac{\tau(kn)}{n^s} = F(s) \zeta(s)^2. \ \ \ (1) $$
A similar treatment has been done with the Dirichlet series $\sum_{n=1}^{\infty}\frac1{\tau(kn)n^s}$ in II.6, page 209 in Tenenbaum's Introduction to Analytic and Probabilistic Number Theory. A link to Google books is here.
For any prime $p$ and an integer $n$, denote by $\nu_p(n)$ the maximal nonnegative integer $a$ with $p^a |n$. (In such case, we write $p^a ||n$. ) Then $$ \tau(kn)=\prod_p (\nu_p(k)+\nu_p(n)+1) $$ where the product runs over all primes. Then we have $$\begin{align} \sum_{n=1}^{\infty} \frac{\tau(kn)}{n^s}&= \prod_p \left( \sum_{v=0}^{\infty} \frac{\nu_p(k)+v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k }\left(\sum_{v=0}^{\infty}\frac{a+v+1}{p^{vs}}\right)\prod_{p\nmid k}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k }\left(\sum_{v=0}^{\infty}\frac{a+v+1}{p^{vs}}\right)\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)^{-1}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right) \prod_{p\nmid k}\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)\\ &=\prod_{p^a||k} \left(\sum_{v=0}^{\infty} \frac{a+v+1}{p^{vs}}\right)\left(\sum_{v=0}^{\infty} \frac{v+1}{p^{vs}}\right)^{-1} \zeta(s)^2\\ &=\prod_{p^a||k} \left(\left( 1-\frac1{p^s}\right)^{-2} +a \left(1-\frac1{p^s}\right)^{-1}\right) \left(1-\frac1{p^s}\right)^2 \zeta(s)^2\\ &=\prod_{p^a||k} \left(1+a\left(1-\frac1{p^s}\right)\right) \zeta(s)^2\\ &=\prod_{p^a||k}\left(1+a -\frac a{p^s}\right) \zeta(s)^2 \end{align} $$ We write $$F(s): = \prod_{p^a||k}\left(1+a -\frac a{p^s}\right):=\sum_{n=1}^{\infty} \frac{f(n)}{n^s}.$$ This is a Dirichlet series with finite number of terms, and we achieved (1).
The formula (1) yields the convolution expression $$ \tau(kn)=\sum_{d|n} f(d)\tau\left(\frac nd\right). $$ Now, we write the summatory function for $\tau(kn)$ as follows: $$ \begin{align} \sum_{n\leq x}\tau(kn) &= \sum_{n\leq x }\sum_{d|n} f(d)\tau\left(\frac nd \right)\\ &=\sum_{d\leq x} f(d) \sum_{m\leq \frac xd} \tau(m) \\ &=\sum_{d\leq x} f(d) D\left( \frac xd \right). \end{align} $$
In the formula $$ \sum_{n\leq x }\tau(kn) = \sum_{d\leq x } f(d) D\left( \frac xd \right), $$ we can compute each $D\left(\frac xd \right)$ in $O(\sqrt x)$ time. Moreover, the sum over $d\leq x$ is in fact a finite sum. We consider the computation times for $f(d)$. This can be done with $O(2^{w(k)})$ multiplications. The number of $d\geq 1$ such that $f(d)\neq 0$ is also $O(2^{w(k)})$. This gives a bound for computation time $O(4^{w(k)} \sqrt x)$.