Du's First Multiplication Sieve

Lemma

$$\forall n\in {\mathbb{Z}}_{+},\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\right|\in \mathcal{O}(\sqrt{n})$$

Proof

$$\begin{array}{rl}\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\right|& \le \left|\left\{\lfloor \frac{n}{d}\rfloor :d\in \{1,2,\dots ,\lfloor \sqrt{n}\rfloor \}\right\}\right|+\left|\left\{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \right\}\cap \{1,2,\dots ,\lfloor \sqrt{n}\rfloor \}\right|\\ & \le 2\sqrt{n}\\ & \in \mathcal{O}(\sqrt{n})\end{array}$$

Let $S_f(n)={\sum }_{k=1}^{n}f(k)$.

Du’s First Multiplication Sieve is an algorithm that computes $S_{f\ast g}(\lfloor \frac{n}{1}\rfloor ),S_{f\ast g}(\lfloor \frac{n}{2}\rfloor ),\dots ,S_{f\ast g}(\lfloor \frac{n}{n}\rfloor )$ for arithmetic functions $f$ and $g$, if $S_f(\lfloor \frac{n}{1}\rfloor ),S_f(\lfloor \frac{n}{2}\rfloor ),\dots ,S_f(\lfloor \frac{n}{n}\rfloor )$ and $S_g(\lfloor \frac{n}{1}\rfloor ),S_g(\lfloor \frac{n}{2}\rfloor ),\dots ,S_g(\lfloor \frac{n}{n}\rfloor )$ are given, in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space.

Algorithm

Lemma

$$\forall n\in {\mathbb{Z}}_{+},S_{f\ast g}(n)=\sum _{d=1}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)$$

Proof

$$\begin{array}{rl}{S}_{f\ast g}(n)& =\sum _{k=1}^n(f\ast g)(k)\\ & =\sum _{k=1}^n\sum _{d\mid k}f\left(\frac{k}{d}\right)g(d)\\ & =\sum _{d=1}^{n}g(d)\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }f(k)\\ & =\sum _{d=1}^{n}g(d)S_f\left(\lfloor \frac{n}{d}\rfloor \right)\end{array}$$

Applying the lemma to find $S_{f\ast g}$ yields an algorithm that solves the problem in $\mathcal{O}(n^{\frac{3}{4}})$ time and $\mathcal{O}(\sqrt{n})$ space.

std::unordered_map<int, int> du(int n, const std::unordered_map<int, int> &sf, const std::unordered_map<int, int> &sg) {
	int m = std::sqrt(n);
 
	std::vector<int> d;
	for (int i = 1; i < m; i++) {
		if (n / (n / i) == i) {
			d.push_back(i);
		}
	}
	for (int i = n / m; i > 0; i--) {
		d.push_back(n / i);
	}
	d.erase(std::unique(d.begin(), d.end()), d.end());
 
	std::unordered_map<int, int> sh;
	for (int i : d) {
		for (int j = 1; j <= i; j = i / (i / j) + 1) {
			sh[i] += (sg.at(i / (i / j)) - (j > 1 ? sg.at(j - 1) : 0)) * sf.at(i / j);
		}
	}
	return sh;
}

Proof

Applying the lemma yields that this algorithm solves the problem in

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)$$

time.

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)\subseteq \mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{k}+\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{\frac{n}{k}}\right)$$

Since

$$\begin{array}{rl}\mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{k}\right)& \subseteq \mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }{n}^{\frac{1}{4}}\right)\\ & =\mathcal{O}(n^{\frac{3}{4}})\end{array}$$

and

$$\begin{array}{rl}\mathcal{O}\left(\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }\sqrt{\frac{n}{k}}\right)& =\mathcal{O}\left(\sqrt{n}\sum _{k=1}^{\lfloor \sqrt{n}\rfloor }{k}^{-\frac{1}{2}}\right)\\ & =\mathcal{O}\left(\sqrt{n}{\int }_0^{\sqrt{n}}{x}^{-\frac{1}{2}}\mathrm{d}x\right)\\ & =\mathcal{O}(n^{\frac{3}{4}})\end{array}$$

it follows that

$$\mathcal{O}\left(\sum _{k\in \{\lfloor \frac{n}{1}\rfloor ,\lfloor \frac{n}{2}\rfloor ,\dots ,\lfloor \frac{n}{n}\rfloor \}}\sqrt{k}\right)\subseteq \mathcal{O}(n^{\frac{3}{4}})$$

Therefore,

$$T(n)\in \mathcal{O}(n^{\frac{3}{4}})$$