Codeforces #519 F. Make It One

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: 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

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

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

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

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


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

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: For avoiding collisions, we pick some primes randomly and compute values over Fp.

According to, 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.