Obviously, such a polynomial exists for $n = 1$. In this case the only condition is that $P(1) = 1$ and the polynomial $P(x) = x$ has this property.

If $n$ is a prime, then its only two divisors are $1$ and $n$. The polynomial $P$ must satisfy the conditions $P(1) = n^2$ and $P(n) = 1$. Let us write $P(x) = ax + b$ and solve the resulting system of equations. We get $P(x) = (-p-1)x + p^2 + p + 1$.

Assume that $n = k \cdot l$ is not a prime and $k, l > 1$. We have $P(1) = n^2$, $P(l) = k^2$, $P(k) = l^2$ and $P(n) = 1$. We know that for arbitrary integers $a$ and $b$ the number $P(a) - P(b)$ is divisible by $a-b$. So, $n-k = k(l-1)$ divides $P(n)-P(k) = 1-l^2 = (1-l)(1+l)$. This implies that $k$ divides $l+1$. Similarly, we show that $n-l$ divides $P(n)-P(l)$. So $l(k-1)$ divides $(1-k)(1+k)$ and $l$ divides $k+1$. Hence, $kl$ divides $(k+1)(l+1)$ and therefore it also divides $(k+1)(l+1) - kl = k+l+1$. We must have $kl \le k+l+1$, which implies that $kl - k - l + 1 \le 2$ or $(k-1)(l-1) \le 2$. We may assume that $k \le l$. The only possible case is $k=2$ and $l=3$, whence $n=6$.

Let us find a polynomial $P$, satisfying the conditions $P(1) = 36$, $P(2) = 9$, $P(3) = 4$ and $P(6) = 1$. For the polynomial $Q(x) = P(x) - 1$ we have $Q(1) = 35$, $Q(2) = 8$, $Q(3) = 3$ and $Q(6) = 0$, so $6$ is a root of $Q$. Let us write $Q(x) = (x-6)R(x)$. For $R(x)$ we have $R(1) = -7$, $R(2) = -2$ and $R(3) = -1$, so $3$ is a root of the polynomial $R(x) + 1$ and $R(x) = 1 + (x-3)S(x)$. For the polynomial $S(x)$ we have $S(1) = 4$ and $S(2) = 3$. We see that $S(x) = 5-x$, whence $P(x) = 1 + (x-6)(1 + (x-3)(x-5))$.