UPD: November 11, 2018

I believe this property always holds, but I haven't shown the correctness yet. For small n, we can check the correctness partially: https://ideone.com/ljg1Ul. Perhaps, the Dirichlet convolution and the Möbius inversion are related to this technique.

Dirichlet convolution - Wikipedia

Möbius inversion formula - Wikipedia

Dirichlet series - Wikipedia

http://codeforces.com/contest/1043

This problem can be solved by the zeta transform and the Möbius transform. The zeta transform is defined as

\begin{align}

\zeta f(i) = \sum_{i \mid j} f(j).

\end{align}

The Möbius transform is defined similarly. Then, the convolution of two sequences is

\begin{align}

(f \ast g) (k) = \sum_{(i,j) = k} f(i)g(j).

\end{align}

Actually,

\begin{align}

\zeta (f \ast g) (k) = \zeta f(k) \zeta g(k).

\end{align}

Thus, we can compute the first n terms of $\underbrace{f\ast\cdots\ast f}_{k}$ in O(n log n + n log k). My solution: http://codeforces.com/contest/1043/submission/45017228. For avoiding collisions, we pick some primes randomly and compute values over Fp.

According to https://en.wikipedia.org/wiki/Diaeresis_(diacritic)#Printing_conventions_in_German, we should type not Mobius but Moebius when we cannot use umlaut letters. Please forgive me.

UPD: In custom invocation of codeforces, the following code always output the same results.

#include <iostream> #include <ctime> #include <random> using namespace std; int main() { cout << time(NULL) << endl; cout << (void *)main << endl; cout << random_device()() << endl; }

You may think we cannot create a random seed, but actually this behavior doesn't appear in the main judge. You can see time(NULL) returns different values.

http://codeforces.com/contest/1043/submission/45564681

http://codeforces.com/contest/1043/submission/45564641