Project Euler Problem 608
Let D(m,n)=displaystylesum{dmid m}sum{k=1}^nsigma0(kd) where d runs through all divisors of m and sigma0(n) is the numbe
Solution
Answer: 439689828
Using the identity
$$\tau(ab)=\sum_{e\mid \gcd(a,b)} \mu(e),\tau(a/e)\tau(b/e),$$
we can rewrite
$$D(m,n) =\sum_{d\mid m}\sum_{k\le n}\tau(kd) =\sum_{e\mid m}\mu(e),H!\left(\left\lfloor \frac ne \right\rfloor\right) \sum_{c\mid m/e}\tau(c),$$
where
$$H(x)=\sum_{k\le x}\tau(k).$$
For $m=200!$, writing
$$200! = \prod_{p\le 200} p^{a_p},$$
the divisor sum factor becomes multiplicative:
$$\sum_{c\mid m/e}\tau(c) = \prod_{p\nmid e}\frac{(a_p+1)(a_p+2)}2 \prod_{p\mid e}\frac{a_p(a_p+1)}2.$$
A fast implementation evaluates the resulting squarefree inclusion–exclusion sum together with the standard $O(\sqrt n)$ divisor-summatory routine for $H(x)$.
The computed value is:
$$D(200!,10^{12}) \equiv 439689828 \pmod{10^9+7}.$$
This matches the known Project Euler result discussion.
Answer: 439689828