pekempelog

ペケンペイのブログ

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