Clearly all the \(f(n)\)s are distinct.

Let the primes be \(p_1,p_2,\cdots,p_k\) in ascending order. Now we prove by induction on \(k\) that for all \(u\), \(\frac{f(p_ku)}{f(u)}\) contains some prime factor at least \(p_k\), while \(f(p_k^N)=C_k p_k^N\) for sufficiently large \(N\).

The base is trivial for \(k=0\). For the induction step, we consider an \(X\) with sufficient powers of \(p_1,p_2,\cdots,p_{k-1}\). By \(\operatorname{LCM}(f(u),f(X))\mid f(uX)\) while \(f(p_ku)\nmid f(uX)\),or \(\frac{f(p_ku)}{f(u)}\nmid \frac{f(uX)}{f(u)}\) we know that the LHS contains a prime factor bigger than \(p_{k-1}\). To conclude the latter, notice that we can now have \(f(p_k^{N+1})\ge p_kf(p_k^N)\), and the strict inequality can happen at most \(\log_{p_{k+1}/p_k}C\) times, which proves the latter.

After the induction, we have if \(v_p(x)>v_p(y)\), then \(v_p (f(x)) > v_p (f(y))\), otherwise we can pick \(Z\) with sufficient prime powers of \(f(x)\) except \(p\), and contradict by \(f(x)|f(yZ)\) and \(x\nmid yZ\). This condition is also sufficient as long as the given numbers don’t contradict divisibility. The proof is simple. For \(x\nmid y\) considering a prime \(p\) with \(v_p(x)>v_p(y)\) we conclude that \(f(x)\nmid f(y)\). To make \(f(x)\mid f(y)\) for all \(x\mid y\), we construct as follows. For each prime and each “layer”(meaning the numbers \(x\) with \(v_p(x)=\text{Const}\)), we can just let the power of \(p\) be the maximum among its descendants(if the layer is empty just make the power all the same, to be the minimal nonexisting integer).

Checking all by brute force works in \(O(n\log (\max a_i)+n \pi (n))\) time.