[Problem proposal] Sum of Multiplicative Function about library-checker-problems HOT 6 OPEN

I forgot to change the permissions. It should be fine now.

By the way, from the practical point of view, experiments on QOJ show that the current $\tilde O(\sqrt n)$ methods are much slower than the $O(n^{2/3} \log^{-4/3} n)$ method below $10^{13}$.

from library-checker-problems.

Related Problems in Library Checker

• https://judge.yosupo.jp/problem/counting_squarefrees
• https://judge.yosupo.jp/problem/sum_of_totient_function

from library-checker-problems.

Thank you for proposing new problems, and many References!!
I only know that they can be computed in O(N^{2/3}) time, so I want to study them soon.

I can't access some of the references. Can you publish them?

I know that some algorithm can compute single partial sum, and some algorithm can compute all $\lfloor N/n \rfloor$-th partial sums.
And both can be used to solve problems in competitive programming.
So I think it is ok to put both version of the problem.

from library-checker-problems.