Mongolian National Mathematical Olympiad

Suppose that such an $f$ exists.
Since $f(b^a)$ and $f(b^b)$ are relatively prime, so are $f(0)$ and $b$. Since $f$ is non-constant polynomial, there exist a prime $p$ and a positive integer $m$ such that $p \mid f(b^{am})$. It is clear that $b$ is relatively prime to $p$. We choose a positive integer $x_0$ such that
$x_0 \equiv am - b^m \pmod p$

and set $n = am + (p-1)x_0$. Then $f(n^a) \equiv f((am - x_0)^a) \equiv f(b^{ma}) \equiv 0 \pmod{p}$. On the other hand, by the Fermat's little theorem, we have
$$f(b^{ma}) \equiv f(b^{am+(p-1)x_0}) \equiv f(b^n) \pmod{p},$$
which gives a contradiction.